一个价格 p(p 为正整数)的不满度定义为: 首先将 p 看做一个由数字组成的字符串(不带前导 0); 然后,如果 p 的最后一个字符是 0,就去掉它。重复这一过程,直到 p 的最后一个字符不是 0; 记 p 的长度为 a,如果此时 p 的最后一位是 5,则不满度为 2a - 1;否则为 2a。 例如,150 的不满度为 3,而 180 则为 4,114514 的不满度为 12。 现在,多莉要卖出一些商品,她能接受的商品价格在 [L, R] 范围内,她希望商品不满度越小越好,请你给出一个不满度最低的价格。用C++实现,如果价格的最小不满度不唯一,则输出价格最低的那一个,1<=L<= R <=10^9
时间: 2024-02-13 08:59:41 浏览: 12
题目分析:
这道题目可以使用二分法来解决。具体来说,我们在区间 $[L,R]$ 中进行二分查找,每次选择区间中点 $mid$,计算 $mid$ 的不满度 $res$,然后根据 $res$ 和目标不满度的大小关系缩小搜索区间。如果 $res$ 小于目标不满度,则左边界变为 $mid+1$;如果 $res$ 大于目标不满度,则右边界变为 $mid-1$。如果 $res$ 等于目标不满度,则可以直接返回 $mid$,因为题目要求价格最低。
需要注意的是,由于不满度的定义与价格的长度有关,因此我们需要计算出价格的最大不满度,即 $2 \log_{10} R + 1$。如果目标不满度大于最大不满度,则直接返回 $-1$,表示不存在满足要求的价格。
代码实现:
下面是 C++ 的代码实现:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
// 计算不满度
int calc(int price) {
string str = to_string(price);
int len = str.size();
// 去掉末尾的 0
while (len > 1 && str[len-1] == '0') {
len--;
str.pop_back();
}
// 判断最后一位是否为 5
if (str[len-1] == '5') {
return 2*len - 1;
} else {
return 2*len;
}
}
// 在区间 [L,R] 中查找不满度为 limit 的最小价格
int search(int L, int R, int limit) {
int maxRes = 2 * log10(R) + 1;
if (limit > maxRes) {
return -1;
}
int left = L, right = R;
while (left <= right) {
int mid = left + (right - left) / 2;
int res = calc(mid);
if (res < limit) {
left = mid + 1;
} else if (res > limit) {
right = mid - 1;
} else {
// 如果找到了目标不满度,则返回最小的价格
while (calc(mid-1) == limit) {
mid--;
}
return mid;
}
}
return -1;
}
int main() {
int L, R;
cin >> L >> R;
int limit;
cin >> limit;
int ans = search(L, R, limit);
cout << ans << endl;
return 0;
}
```
代码解析:
我们首先定义了一个函数 calc,用于计算价格的不满度。它的实现与上一个问题的实现相同。
接着,我们定义了一个函数 search,用于在区间 $[L,R]$ 中查找不满度为 limit 的最小价格。我们首先计算出价格的最大不满度 maxRes,如果目标不满度大于 maxRes,则直接返回 $-1$。否则,我们在区间 $[L,R]$ 中进行二分查找,每次选择区间中点 $mid$,计算 $mid$ 的不满度 $res$,然后根据 $res$ 和目标不满度的大小关系缩小搜索区间。如果 $res$ 小于目标不满度,则左边界变为 $mid+1$;如果 $res$ 大于目标不满度,则右边界变为 $mid-1$。如果 $res$ 等于目标不满度,则我们需要找到最小的价格,因此我们从 $mid$ 开始向左查找,直到找到不满度小于目标不满度的价格,然后返回该价格。如果在二分查找过程中没有找到满足要求的价格,则返回 $-1$。
在 main 函数中,我们读入区间 $[L,R]$ 和目标不满度,然后调用 search 函数进行查找。如果找到了满足要求的价格,则输出该价格,否则输出 $-1$。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)