A27703. 载重(load)
填空题
中等
知识点
题目描述
载重(load)
题目描述
某星球发生灾难，他们需要乘坐飞船逃离该星球，该星球有N个居民，已经排好队，要求按照队伍的顺序登船，飞船只能飞行M趟，为了控制成本，需要将飞船的承重设计的尽可能的小；给定N个居民的体重，求飞船的承重。
输入格式
第一行两个整数N和M，意义如题所述；
第二行，N个整数，表示居民的体重，
输出格式
一个整数，意义如题所述。
输入输出样列
输入样例1
8 3
40 30 50 80 100 120 40 60
输出样例1
220
说明
数据范围1<=N<=1000000;
1<=M<=100000;
参考答案
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i ++ )
#define DOR(i, a, b) for(int i = b; i >= a; i -- )
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
int a[N], n, m, l = 1, r;
bool check (int x) {
int s = 0, c = 1;
for (int i = 1; i <= n; i ++ )
if (s + a[i] > x) c ++, s = a[i];
else s += a[i];
return c <= m;
}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i]; r += a[i];
}
while (l < r) {
int mid = l + r >> 1;
if (check (mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
上一题
下一题