本文主要是介绍poj-3273-Monthly Expense-二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你n m
然后给你n个数。让你把这n个数分为m个部分，每个部分都是连续的。问所有部分中的最大值最小的值。
做法：
二分。一开始上届是n个数的和。代表只分一组。
下届是n个数中最大的数。代表分n组；
如果结果是mid=（上届+下届）/2；那么根据mid看看能分多少组。组数大于m，代表mid比实际值小。下届变成mid+1。否则，上届变成mid-1；
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[100100];
int n,m;
int sw(int mid)
{int s,num,i;s=0;num=1;for(i=0;i<n;i++){if(s+a[i]<=mid){s+=a[i];}else{s=a[i];num++;}}if(num>m)return 1;else return 0;
}
int main()
{int l,r,i,mid;cin>>n>>m;r=0;l=0;for(i=0;i<n;i++){scanf("%d",&a[i]);r+=a[i];if(a[i]>l)l=a[i];}mid=(l+r)/2;while(l<r){if(sw(mid))l=mid+1;else r=mid-1;mid=(l+r)/2;}cout<<mid<<endl;return 0;}这篇关于poj-3273-Monthly Expense-二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
