若要使用二分
时间: 2023-07-11 18:11:46 浏览: 39
如果要使用二分的话,我们需要先确定二分的上下界。
对于下界,由于价格不能为0,因此我们可以将下界设为1。
对于上界,如果我们直接将上界设为 R 的话,那么二分的范围可能会很大,导致时间复杂度过高。因此,我们需要找到一个比较紧凑的上界,使得二分的范围尽可能小。
根据题目中不满度的定义,我们可以发现,不满度主要与价格的长度有关系,而与价格的具体大小无关。因此,我们可以将上界设为 R 的位数加上1,这样就可以保证不会漏掉任何一个满足条件的价格。
接下来,我们就可以开始二分了。首先将下界设为1,上界设为 R 的位数加上1。每次取中点 mid,计算 mid 的不满度 unhappiness,如果 unhappiness 小于目标不满度,那么说明 mid 不满足条件,下一次就要在右半区间继续二分;如果 unhappiness 大于等于目标不满度,那么说明 mid 及其左边的所有价格都不满足条件,下一次就要在左半区间继续二分。如果 unhappiness 等于目标不满度,那么说明 mid 可能是一个满足条件的价格,暂时将它保存下来,并继续在左半区间继续二分,直到找到最小的满足条件的价格为止。
代码实现如下:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int getUnhappiness(int price) {
string s = to_string(price);
int len = s.length();
while (s[len-1] == '0') {
s.erase(len-1);
len--;
}
if (s[len-1] == '5') {
return 2 * len - 1;
}
else {
return 2 * len;
}
}
int main() {
int L, R;
cin >> L >> R;
int targetUnhappiness = 0x7fffffff;
int targetPrice = 0;
int left = 1;
int right = to_string(R).length() + 1;
while (left <= right) {
int mid = (left + right) / 2;
int unhappiness = getUnhappiness(mid);
if (unhappiness < targetUnhappiness) {
targetUnhappiness = unhappiness;
targetPrice = mid;
}
if (unhappiness < getUnhappiness(L)) {
left = mid + 1;
}
else if (unhappiness >= getUnhappiness(R)) {
right = mid - 1;
}
else {
int curPrice = mid;
while (getUnhappiness(curPrice) == targetUnhappiness) {
targetPrice = curPrice;
curPrice--;
}
break;
}
}
cout << targetPrice << endl;
return 0;
}
```
首先读入价格范围 [L, R],初始化目标不满度为一个较大的数(0x7fffffff),目标价格为0,下界为1,上界为 R 的位数加上1。
接下来,进入二分循环,每次取中点 mid,计算 mid 的不满度 unhappiness。如果 unhappiness 小于目标不满度,那么说明 mid 不满足条件,下一次就要在右半区间继续二分;如果 unhappiness 大于等于目标不满度,那么说明 mid 及其左边的所有价格都不满足条件,下一次就要在左半区间继续二分。如果 unhappiness 等于目标不满度,那么说明 mid 可能是一个满足条件的价格,暂时将它保存下来,并继续在左半区间继续二分,直到找到最小的满足条件的价格为止。
最后输出目标价格即可。
时间复杂度为 O(log(R-L+1)),比直接枚举要快得多。