一道分块处理的题目

我们来看一下这个题目：

Joker Xue想要租房子，而他的心上人对数字十分敏感。他发现，对于一间租金为p元/月的房子，他的心上人的心理不悦度是这样计算的：

1. 首先将 p 看做一个由数字组成的字符串（不带前导 0）；
2. 然后，如果 p 的最后一个字符是 0，就去掉它。重复这一过程，直到 p 的最后一个字符不是 0；
3. 记 p 的长度为 a，如果此时 p 的最后一位是 5，则不悦度为 2a−1；否则为 2a。

例如，850 代表的不悦度为 3，而 880 则为 4，9999 为 8。

Joker Xue想要在T个不同的地区租房子，在每个地区他都有一个租金的心理预期 [L, R] ，现在他想要知道在这些地区能够使得心上人心理不悦度最低并且租金较低的方案。

Joker Xue要去准备他的“万兽之王”演唱会，所以请聪明的你帮忙进行最优解的计算。

输入格式

输入文件的第一行包含一个正整数 T，表示Joker Xue想要租房子的地区的数量。

接下来的T行，每行包含两个空格分隔的正整数 L,R，表示他的租金心理预期。

输出格式

对于每个地区，在单独的一行内输出能使心上人的心理不悦度最低的租金值。如果结果不唯一，则输出最小的那个。

样例

输入

3
998 1002
998 2002
4000 6000

输出

1000
1000
5000

数据范围

• 对于 20%的数据，L,R≤2000；
• 对于 100% 的数据，T≤100，1 ≤L≤ R ≤ 1e9。

这是我们学校ACMOJ上面的一道题，以下是题目链接：

租购 · ACMOJ

我们来分析以下这个题目，我们根据数据规模可以很轻松地判断出这里不能够直接遍历，因为时间不够，那么从常用的角度来说，就是剩下了两种时间复杂度$O(\log n)和O(\sqrt n)$（常数级的时间复杂度我们就不考虑了，其实笔者的一个朋友有相关的想法，但是没有最后实践成功，后续笔者可能会继续想一想这个问题），在这里面我们不难发现，对数级的时间复杂度固然更为简便，但是似乎没有合适的算法来实现，我们自然而然就会往根号级的算法去想，而最为直接的根号级算法，就是分块处理：

我们来思考一下，其实我们先明确一点，我们将p所有计入不悦度运算的位数称为有效位，那么我们可以很明显地看出，有效位是越少越好的，而且有效位少的优先级应该比末尾是5的有限级更高，因为末尾是5，结果只是在原有基础上-1，而如果有效位能够少一个，那么不悦度的结果可以-2

那我们达成共识，现在可行的范围内找有效位尽可能少的，然后在有效位已经最少的情况下，看看有效位的末尾能不能取到5。

这是我们处理的原则，那么接下来如何分块呢？

我们先想一下r - l的范围，如果r - l小于1e5，那么我们其实可以直接范围内的数进行遍历，计算出每一个数的不悦度，这样就比较，取最小，最后计算机的计算次数差不过是在1e6这个级别的，不会有超时的情况。

那如果r - l大于1e5呢？那是不是在区间之间，至少存在一个后五位都是0的数，那我们实际上，后5位存在非零数位的数，必然不会符合我们的最优要求，所以我们只要将r和l都除以1e5，然后再在新得到的区间里面遍历就可以了，这个算法的复杂度计算次数大概是1e9/1e5=1e4这个级别的，算上我们的操作数，至多也就在1e5级别，比我们上一种情况的遍历还要更快速一些。

OK，理论可行，接下来就是具体实现了，细节方面还有很多要考虑的，之前笔者在交这道题的时候好多次都WA了，就是因为有些细节没有考虑清楚。

我们先来设计一个直接计算不悦度的函数：

int byd(long long x){
	int cnt = 0;
	while(x%10 == 0)
		x /= 10;
	bool flag = false;
	if(x%10 == 5)
		flag = true;
	while(x > 0){
		x /= 10;
		cnt++;
	}
	cnt = cnt * 2 - flag;//flag为true，那么相当于多尾数是5，在原有基础上-1
	return cnt;
}

函数名我的设计理念就是“不悦度”汉语拼音的缩写（bu）（yue）（du），请不要产生无端联想~

我们再来设计一个solve()函数，直接解决从l到r的范围问题：

long long solve(long long l,long long r){
	long long ans1 = l;
	int ans2 = byd(l);
	for(long long i = l;i <= r; i++){
		int tmp = byd(i);
		if(tmp < ans2){
			ans1 = i;
			ans2 = tmp;
		}
	}
	return ans1;
}

基本上就是最简单的判断，没有什么好说的

我们再来写一下main()函数，记住其中有很多非常容易错的细节：

const long long N = 1e5;
int main()
{
	int n;
	cin >> n;
	for(int i = 0;i < n; i++){
		long long l, r;
		cin >> l >> r;
		long long x = r - l;
		if(x <= N)
			cout << solve(l,r) << endl;//如果小于1e5，那么直接丢给solve()
		else{
			if(l < N){//这里就是第一种特殊情况，如果l比1e5小，那么l就不能直接处理，需要进行判断
				if(r >= 5 * N)//因为你的x是大于1e5的，所以r至少是一个五位数，五位数中不悦度最低的就是5*1e5，但我们不能确保r的范围能够到达那个程度，我们还要基于此做一次判断
					cout << solve(l, 5 * N) << endl;
				else
					cout << solve(l, r) << endl;
			}
			else{
				if(l % N == 0)//这里需要记住，在/1e5之后，我们的l应该是向上取整的，r是向下取整的，所以l还要对于边界判断
					l /= N;
				else{
					l /= N;
					l++;
				}
				r /= N;//r是向下取整，符合C++中的除号运算符
				cout << solve(l,r) * N << endl;
			}
		}
	}
	return 0;
}

我们将三段代码合并到一块，就可以得到AC的结果（笔者实测过）：

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5;
int byd(long long x){
	int cnt = 0;
	while(x%10 == 0)
		x /= 10;
	bool flag = false;
	if(x%10 == 5)
		flag = true;
	while(x > 0){
		x /= 10;
		cnt++;
	}
	cnt = cnt * 2 - flag;//flag为true，那么相当于多尾数是5，在原有基础上-1
	return cnt;
}
long long solve(long long l,long long r){
	long long ans1 = l;
	int ans2 = byd(l);
	for(long long i = l;i <= r; i++){
		int tmp = byd(i);
		if(tmp < ans2){
			ans1 = i;
			ans2 = tmp;
		}
	}
	return ans1;
}
int main()
{
	int n;
	cin >> n;
	for(int i = 0;i < n; i++){
		long long l, r;
		cin >> l >> r;
		long long x = r - l;
		if(x <= N)
			cout << solve(l,r) << endl;//如果小于1e5，那么直接丢给solve()
		else{
			if(l < N){//这里就是第一种特殊情况，如果l比1e5小，那么l就不能直接处理，需要进行判断
				if(r >= 5 * N)//因为你的x是大于1e5的，所以r至少是一个五位数，五位数中不悦度最低的就是5*1e5，但我们不能确保r的范围能够到达那个程度，我们还要基于此做一次判断
					cout << solve(l, 5 * N) << endl;
				else
					cout << solve(l, r) << endl;
			}
			else{
				if(l % N == 0)//这里需要记住，在/1e5之后，我们的l应该是向上取整的，r是向下取整的，所以l还要对于边界判断
					l /= N;
				else{
					l /= N;
					l++;
				}
				r /= N;//r是向下取整，符合C++中的除号运算符
				cout << solve(l,r) * N << endl;
			}
		}
	}
	return 0;
}

后来笔者与舍友讨论，应该还会存在常数级算法的可能，但是笔者没有能够实现，如果有读者愿意和笔者交流常数级算法的可能性，笔者将不胜感激。

感谢 @Geniustanker 与笔者的讨论，这个题目也是他提供给笔者的。