POJ 3273 Monthly Expense(二分)

本文主要是介绍POJ 3273 Monthly Expense(二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:点击打开链接

题目大意是说给n个数,要求分成m组,必须连续的数才能合并成一个组,求满足ans大于等于每一组的和的最小ans(每个组可以只有1个数)

显然二分查找最小的ans

//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstring>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define sqrt(n) sqrt((double)n)
#define pow(a,b) pow((double)a,(int)b)
#define inf (1<<29)
#define NN 100005
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;
//一样的思想,暴力的遍历每一个可能的答案,check是否满足,找到满足的最小的,于是二分
int n,m;//n个数分m组
int a[NN];
bool ok(int ans)//判断答案能否分m组
{//........分组连续......贪心,只要连续的加起来没有超过ans就可以分到一个组int k = 1;//傻了...for (int i = 0,sun = 0;i < n;i++){if (sun + a[i] <= ans) sun += a[i];else{k++;if (k > m) return 0;//剪枝sun = a[i];}}return k <= m;//能分6组的话分7组是绰绰有余滴,小于m组的也可以分成m组
}
int main()
{while (~scanf("%d%d",&n,&m)){int l = 0,r = 0;for (int i = 0;i < n;i++){scanf("%d",a+i);r += a[i];l = max(l,a[i]);}int mid = (l+r)>>1;while (l < r){if (ok(mid))//OK只说明mid满足 但是不一定最小r = mid - 1;//尝试更小的midelse l = mid + 1;//不满足就尝试更大的midmid = (l+r)>>1;}cout<<mid<<endl;}return 0;
}

这篇关于POJ 3273 Monthly Expense(二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---