59 lines
1.1 KiB
C++
59 lines
1.1 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <algorithm>
|
||
//基本策略->
|
||
//二分查找 mid = (low + high) / 2
|
||
//贪婪验证 是否存在分组方式
|
||
|
||
using namespace std;
|
||
|
||
bool check(const vector<int>& a, int target, int k) {
|
||
int js = 1; // 当前分配了1个抄写员
|
||
int temp = 0; // 当前抄写员工作量
|
||
|
||
for (int i = 0; i < a.size(); i++) {
|
||
if (a[i] > target) return false; // 单个书页超过 target，不可行
|
||
if (temp + a[i] > target) { // 超过 target，换一个抄写员
|
||
js++;
|
||
temp = a[i];
|
||
} else {
|
||
temp += a[i];
|
||
}
|
||
}
|
||
|
||
return js <= k; // 是否可行
|
||
}
|
||
|
||
int main(){
|
||
int n, k;
|
||
cin >> n >> k;
|
||
vector<int> arr;
|
||
arr.resize(n);
|
||
|
||
int max = 0;
|
||
int sum = 0;
|
||
for(int i = 0; i < n; i++){
|
||
cin >> arr[i];
|
||
if(max < arr[i]) max = arr[i];
|
||
sum += arr[i];
|
||
}
|
||
|
||
int left = max;
|
||
int right = sum;
|
||
int result = right;
|
||
|
||
while (left <= right) {
|
||
int mid = left + (right - left) / 2;
|
||
if (check(arr, mid, k)) {
|
||
result = mid;
|
||
right = mid - 1;
|
||
} else {
|
||
left = mid + 1;
|
||
}
|
||
}
|
||
|
||
cout << result << endl;
|
||
|
||
return 0;
|
||
}
|