NYOJ 680 摘枇杷（二分搜索+贪心）

摘枇杷

描述

理工学院的枇杷快熟了，ok，大家都懂得。而且大家都知道，学校的枇杷树都是一列一列的。现在小Y同学已经在筹划怎么摘枇杷了。现在我们假设有一列枇杷树，而且每棵枇杷树上枇杷果的数量小Y都已经知道了。

假设现在有n棵枇杷树，小Y可以把这n棵枇杷树分成m组，每组枇杷果的数量是这组内每棵枇杷树上枇杷果数量的和。注意，每组的枇杷树必须是连续的。（每组最少1棵树，最多n棵树）。小Y把枇杷往寝室拿的时候是一组一组拿的，所花费的力气等于这m组中枇杷果最多的那组枇杷果的数量。现在小Y想花尽量少的力气把这些枇杷果拿回寝室。

输入

多组测试数据，以EOF结束（<= 100组）
每组测试数据第一行有两个数n（n <= 1000）和m（1 <=m <= n）
第二行有n个数，分别代表每颗树上枇杷果的数量

输出

输出小Y同学所花费的最小的力气，每个结果占一行。

样例输入

3 2
1 2 3
7 5
1 4 3 1 5 2 4

样例输出

3
5

这是一个最大值最小化的问题。二分枚举最终答案即可。

#include
#include
using namespace std;
const int N = 1005;
int a[N], Max, sum, n, m;bool judge(int x)
{int s = 0, cnt = 0;for(int i = 0; i < n; i++){if(a[i] > x)return false;if(s + a[i] > x){cnt++;s = a[i];if(cnt > m - 1)return false;}elses += a[i];}return true;
}int get_ans()
{int l = Max, r = sum;while(l <= r){int mid = (l + r) / 2;if(judge(mid))r = mid - 1;elsel = mid + 1;}return l;
}int main()
{while(~scanf("%d%d",&n,&m)){sum = 0, Max = 0;for(int i = 0; i < n; i++){scanf("%d",&a[i]);sum += a[i];Max = max(Max, a[i]);}printf("%d\n",get_ans());}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！