一个价格 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 17:00:04 浏览: 10
题目分析:
根据题意,我们需要找到一个价格,使得它的不满度最小,那么我们可以从小到大枚举价格,对于每个价格,我们可以根据题目中的算法计算它的不满度,然后取最小值即可。但是,如果有多个价格的不满度都是最小的,那么我们需要输出价格最低的那一个,因此我们需要记录当前最小的不满度以及对应的价格。
代码实现:
```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 minUnhappiness = 0x7fffffff;
int minPrice = 0;
for (int i = L; i <= R; i++) {
int unhappiness = getUnhappiness(i);
if (unhappiness < minUnhappiness) {
minUnhappiness = unhappiness;
minPrice = i;
}
}
cout << minPrice << endl;
return 0;
}
```
首先读入价格范围 [L, R],初始化最小不满度为一个较大的数(0x7fffffff),最小价格为0。
接下来,从 L 开始到 R 结束,枚举所有的价格,对于每个价格,计算它的不满度,如果它的不满度比当前最小不满度小,就更新最小不满度和最小价格。
最后输出最小价格即可。
时间复杂度为 O(R-L+1),可以通过本题。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![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)