消费者对于商品的价格会有一个不满度。一个价格 p(p 为正整数)的不满度定义为: 首先将 p 看做一个由数字组成的字符串(不带前导 0); 然后,如果 p 的最后一个字符是 0,就去掉它。重复这一过程,直到 p 的最后一个字符不是 0; 记 p 的长度为 a,如果此时 p 的最后一位是 5,则不满度为 2a - 1;否则为 2a。 例如,150 的不满度为 3,而 180 则为 4,114514 的不满度为 12。 现在,多莉要卖出一些商品,她能接受的商品价格在 [L, R] 范围内,她希望商品不满度越小越好,请你给出一个不满度最低的价格。1<=L<= R <=10^9.用C++实现,并使用二分法来查询不满度最低的价格
时间: 2024-02-13 09:03:22 浏览: 23
好的,以下是使用二分法查询不满度最低价格的 C++ 代码实现。具体思路是:在 [L, R] 范围内二分查找最小的不满度,如果当前中间值的不满度比上一个中间值的不满度更小,那么继续在左侧查找,否则在右侧查找。直到找到不满度最小的价格。
```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;
}
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;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)