题目描述

《卡车装货》

【卡车装货】 现在有n组货物需要通过卡车运送，每组货物的量可以用一个整数ai表示。 我们用数组a=[a1, a2, ..., an]表示n组货物的量。一组货可以被分到多量卡车上进行运送。 但是，不同组的货不能混装到同一辆卡车上。现在我们希望所有的货物可以用至多m辆卡车来运送。 问：当卡车的运载量最少为多少时可以满足这一要求？保证m>=n（否则一定无解）。 【输入样例】 5 10 4 42 40 26 46 【输出样例】 21 /* 【注意】 数组a不保证已经排序 */ #include //#include using namespace std; int a[100010]; // 货物量数组 int n,m; // 条件验证函数C(x) ：卡车载货量x的情况下， // m辆卡车如果能装完a[n]指定的货，则返回true,否则返回false。 bool C(int x){ int cnt = 0; // 计算装完n组货至少需要多少量卡车 for(int i=1;i<=n;i++) cnt += (a[i]+x-1)/x; // 正整数相除的向上取整 //cnt += ceil((a[i]1.0)/x); if( cnt > m) //需要的卡车数量>m,即m辆车装不下 return false; else return true; } // 在min~max中二分查找使C（x）成立的最小值 / <x部分都是不能满足题目条件的

=x，都能满足 临界值x是满足部分的最小值，是要找的答案。 这种情况通常叫求解“最大值最小” 。 / int find(int min, int max) { int left = min, right = max; // 初始卡车装载量的查找范围 int ans; while (left <= right) { int mid = (left + right) / 2; // 中间数的位置 if ( C(mid) ){ // 条件成立，答案在左半区间 right = mid - 1; ans = mid; // 记录可能的答案 } else{ // 条件不成立，答案在右边区间 left = mid + 1; } } // 最终答案在ans中 return ans; } int main(){ int max = 0; // 最大值 cin >> n >> m; for(int i=1; i<=n; i++){ cin >> a[i]; if(a[i] > max) max = a[i]; } cout << find(0, max); return 0; } / 【输入用例2】 3 5 4 7 5 【输出用例2】 4 【输入用例3】 4 4 10 20 30 40 【输出用例3】 40

输入格式

无

输出格式

（见样例）

样例

输入样例 1

5 10
4 42 40 26 46

输出样例 1

21

输入样例 2

3 5
4 7 5

输出样例 2

4

输入样例 3

4 4
10 20 30 40

输出样例 3

40