不满度并不是简单单调递增的,所以不能如此二分
时间: 2023-10-26 21:06:05 浏览: 32
是的,你说得对。因为不满度并不是简单单调递增的,所以我们需要进行一些修改,使得该算法能够正确地找到不满度最小的价格。
具体来说,我们需要考虑以下三种情况:
1. 如果 mid 的不满度小于 ans,那么更新 ans 的值为 mid 的不满度。
2. 如果 mid 的不满度等于 ans,那么更新 ans 的值为 min(ans, mid)。
3. 如果 mid 的不满度大于 ans,那么在 mid 的左侧或右侧继续查找。
下面是修改后的 C++ 代码实现:
```cpp
#include <iostream>
#include <string>
using namespace std;
int getUnsatisfaction(int price) {
string s = to_string(price);
while (s.back() == '0') {
s.pop_back();
}
int len = s.length();
if (s.back() == '5') {
return 2 * len - 1;
}
return 2 * len;
}
int main() {
int L, R;
cin >> L >> R;
int ans = -1;
int left = L, right = R;
while (left <= right) {
int mid = left + (right - left) / 2;
int unsatisfaction = getUnsatisfaction(mid);
if (unsatisfaction < ans || ans == -1) {
ans = unsatisfaction;
} else if (unsatisfaction == ans) {
ans = min(ans, unsatisfaction);
}
if (mid > L && getUnsatisfaction(mid - 1) <= unsatisfaction) {
right = mid - 1;
} else if (mid < R && getUnsatisfaction(mid + 1) <= unsatisfaction) {
left = mid + 1;
} else {
break;
}
}
cout << ans << endl;
return 0;
}
```
在上述代码中,我们首先将 ans 的初始值设置为 -1,表示还没有找到最小的不满度。然后在每次二分时,根据 mid 的不满度更新 ans 的值。如果 mid 的不满度小于 ans,那么更新 ans 的值为 mid 的不满度;如果 mid 的不满度等于 ans,那么更新 ans 的值为 min(ans, mid);如果 mid 的不满度大于 ans,那么在 mid 的左侧或右侧继续查找。
最后输出 ans 的值,即为不满度最小的价格。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)