花费(cost.cpp) 某人的旅行天数为 N(1≤N≤100 000),每天需要花的钱已经分配好,请把这些天分成 M(1≤M≤N)份(每份都是连续的天),则第 i 段的钱数和为 sum[i](i=1,2,…,M), 求 max{sum[i]}最小为多少?
时间: 2024-04-18 17:27:35 浏览: 18
要求 max{sum[i]} 最小,可以采用二分法来解决这个问题。
首先,计算出 sum 数组的最大值和总和。最大值的下界为 max(sum),上界为总和。
然后,在这个范围内进行二分查找。每次取中间值 mid,假设它是 max{sum[i]} 的一个候选解。
接下来,遍历 sum 数组,累加每天的花费,当累加值超过 mid 时,重新计数,并将计数器加一。
如果计数器的值大于 M,说明 mid 偏小,更新下界为 mid + 1,否则说明 mid 偏大,更新上界为 mid。
最终,当上界等于下界时,即找到了最小的 max{sum[i]}。
以下是一个示例的 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool check(vector<int>& sums, int M, int mid) {
int count = 1;
int currSum = 0;
for (int i = 0; i < sums.size(); i++) {
if (sums[i] > mid) {
return false;
}
if (currSum + sums[i] > mid) {
count++;
currSum = sums[i];
} else {
currSum += sums[i];
}
}
return count <= M;
}
int minMaxSum(vector<int>& costs, int M) {
int left = *max_element(costs.begin(), costs.end());
int right = accumulate(costs.begin(), costs.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (check(costs, M, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
int N, M;
cin >> N >> M;
vector<int> costs(N);
for (int i = 0; i < N; i++) {
cin >> costs[i];
}
int result = minMaxSum(costs, M);
cout << result << endl;
return 0;
}
```
这段代码中,首先输入旅行天数 N 和分段数 M,然后输入每天的花费。最后输出最小的 max{sum[i]}。
希望对你有帮助!如有其他问题,请随时提问。
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)