本文主要是介绍POJ3273 二分与最大值最小化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给出农夫在n天中每天的花费,要求把这n天分作m组,每组的天数必然是连续的,要求分得各组的花费之和应该尽可能地小,最后输出各组花费之和中的最大值
要点:
与二分求最小值最大化一样,还是先猜测一个数mid进行比较,然后二分减小区间,过oj的时候RE了好几次,后来才发现是数组区间开小一位了,注意RE也有可能是这种情况
#include<stdio.h>
#include<string.h>
#define maxn 100005
int a[maxn];
int m, n;int main()
{int i,mid,step;while (scanf("%d%d", &n,&m)!=EOF){int left = 0,right=0;for (i = 1; i <= n; i++){scanf("%d", &a[i]);if (a[i] > left)left = a[i];right += a[i];}while(left<=right){int sum = 0, num = 1;//初始把所有天数作为一组mid = (left + right) / 2;for (i = 1; i <= n; i++){if (sum + a[i] <= mid)//如果小于等于就可以加入a[i]sum += a[i];else //如果超过mid就重置sum从a[i]开始{sum = a[i];num++; //超过mid作为前面的组数+1,最后的不用+1}}if (num > m) //组数多说明区间开小了(易错)left = mid + 1;else //组数相同或小说明区间开大了{right = mid - 1;step = mid;}}printf("%d\n", step);}return 0;
}
这篇关于POJ3273 二分与最大值最小化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!