如果使用二分法优化呢
时间: 2023-07-24 09:11:14 浏览: 55
是的,使用二分法可以大大优化时间复杂度。
我们可以注意到,不满度的值是随着价格的增加而单调递增的,因此可以使用二分法来查找最小不满度对应的价格。具体实现如下:
```c++
#include <iostream>
#include <string>
using namespace std;
int calc_unsatisfy(string price) {
int len = price.size();
while (len > 0 && price[len - 1] == '0') {
len--;
price.pop_back();
}
if (len == 0) return 1; // 特判价格为 0 的情况
if (price[len - 1] == '5') return 2 * len - 1;
else return 2 * len;
}
int find_best_price(int L, int R) {
int min_unsatisfy = 1000000000;
int best_price = 0;
while (L <= R) {
int mid = (L + R) / 2;
string price = to_string(mid);
int unsatisfy = calc_unsatisfy(price);
if (unsatisfy < min_unsatisfy) {
min_unsatisfy = unsatisfy;
best_price = mid;
}
if (unsatisfy == min_unsatisfy) {
// 如果不满度相同,选择价格较小的那个
best_price = min(best_price, mid);
}
if (mid < R && calc_unsatisfy(to_string(mid + 1)) <= min_unsatisfy) {
// 如果 mid 不是 R,且 mid + 1 的不满度不比 min_unsatisfy 小,
// 则可以将搜索范围缩小到 [mid + 1, R]
L = mid + 1;
} else if (mid > L && calc_unsatisfy(to_string(mid - 1)) <= min_unsatisfy) {
// 如果 mid 不是 L,且 mid - 1 的不满度不比 min_unsatisfy 小,
// 则可以将搜索范围缩小到 [L, mid - 1]
R = mid - 1;
} else {
// 如果无法缩小搜索范围,则已经找到最小值
break;
}
}
return best_price;
}
int main() {
int L, R;
cin >> L >> R;
int best_price = find_best_price(L, R);
cout << best_price << endl;
return 0;
}
```
这个算法的时间复杂度是 O(log R * log R),其中二分查找的时间复杂度为 O(log R),字符串处理的时间复杂度为 O(log R)。在实际应用中,该算法的效率更高,可以处理更大的数据规模。
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)