本文共 811 字,大约阅读时间需要 2 分钟。
题意比较明确:求n棵树分成m组中最小力气花费的最大值
此题同nyoj-568(疯牛)&&nyoj-619(青蛙过桥) 解法类似再次不在多做解释
#include#include int n,m;int a[1005];bool Greedy(int x){ int temp = 0,k = 0; for(int i = 0;i < n;i++) { if(a[i] > x) return false; temp += a[i]; if(temp > x) { i--;k++; temp = 0; } } k++; if(k <= m) return true; return false;}int search(int x,int y){ while(x <= y) { int mid = (x + y) / 2; if(Greedy(mid)) y = mid - 1; else x = mid + 1; } return x;}int main(){ while(~scanf("%d%d",&n,&m)) { int sum = 0,max = 0; for(int i = 0;i < n;i++) { scanf("%d",&a[i]); if(max < a[i]) max = a[i]; sum += a[i]; } printf("%d\n",search(max,sum)); }}
转载地址:http://iysgi.baihongyu.com/