ALDS1_4_D 2018-2-22

本文主要是介绍ALDS1_4_D 2018-2-22，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL A[100000 + 10];
int n, k;
//模拟装货过程
bool check(LL P) {int cnt = k;for (int i = 0; i < n; ) {LL t = P;cnt--;// 卡车已经用完，证明卡车当前最大装载量不能装完货物if (cnt < 0)return false;while (i < n && t >= 0) {// 剩余重量可以装上当前货物if (t >= A[i])t -= A[i],i++;//装不下则用下一辆卡车去装if (t < A[i])break;}}return true;
}
// 二分找出P的最小值
LL BinarySearch(LL sum) {LL left = 0, right = sum;LL mid;while (left + 1 < right) {mid = (left + right) / 2;//可以装好货物if (check(mid))right = mid;elseleft = mid;}return right;
}
int main() {LL sum = 0;scanf("%d %d", &n, &k);for (int i = 0; i < n; i++) {scanf("%lld", &A[i]);sum += A[i];}LL P = BinarySearch(sum);printf("%lld\n", P);return 0;
}

这篇关于ALDS1_4_D 2018-2-22的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---