本文主要是介绍POJ3273-Monthly Expense (最小化最大值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：click here~~
【题目大意】
农夫JF在n天中每天的花费，要求把这n天分作m组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值
【解题思路】：
经典的最小化最大值问题，要求连续的m个子序列，子序列的和最大值的最小，枚举满足条件的m的最小值即为答案，因此二分查找。
1.是否能把序列划分为每个序列之和不大于mid的m个子序列,
2.通过用当前的mid值能把天数分成几组，
3.比较mid和t的大小，从而确定mid
具体见代码吧：
//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m,num[N];
bool is_part(int mid)
{int t=0,s=0; //t==当前mid值能把n天分成的组数(初始把全部天数作为0组) bool ok=true;for(int i=0; i<n; i++)//遍历每一天的花费{if(num[i]>mid){//如果某个值大于，显然不符合ok=false;break;}if(s+num[i]>mid){//不能再把当前元素加上了t++;s=num[i]; //把前i天作为一组if(t>m-1){ //t=m时退出，即在最后一个元素之前都已经用了m条划分线ok=false;break;}}else s+=num[i];//把当前元素与前面的元素加上，以便尽量往右划分，贪心到底}return ok;
}
void judge() //二分查找
{int ll=0,rr=1e8;while(ll<rr){int mid=(ll+rr)>>1;if(is_part(mid)) rr=mid;else ll=mid+1;}printf("%d\n",ll);
}
int main()
{int maxx=0,sum=0;scanf("%d%d",&n,&m);for(int i=0; i<n; i++){scanf("%d",&num[i]);sum+=num[i];maxx=max(maxx,num[i]);}if(m==n||m==1) printf("%d\n",maxx);else judge();return 0;
}这篇关于POJ3273-Monthly Expense (最小化最大值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
