首页 > 代码库 > poj 3273 Monthly Expence 简单二分
poj 3273 Monthly Expence 简单二分
1 /** 2 大意: 有连续的n天,每一天有一定的花费,将其分成m份,每一份占一天或者连续的几天,求这m份中的最大值 3 思路: 二分其最大上限,看在此最大上线,能分成多少份,若大于m份,说明上限过小,需要扩大上限 4 若小于m份,则说明,下限过大,需要缩小上限。 5 **/ 6 #include <iostream> 7 8 using namespace std; 9 int c[100010]; // 记录,每天的花费 10 int main() 11 { 12 int n,m; 13 cin>>n>>m; 14 int maxn =0,sum =0; 15 for(int i=1;i<=n;i++){ 16 cin>>c[i]; 17 if(c[i]>maxn) maxn = c[i]; 18 sum += c[i]; 19 } 20 21 int mid ,low = maxn,high= sum; 22 while(high>low){ 23 mid = (high + low )/2; 24 int cnt = 1,w =0; 25 for(int i=1;i<=n;i++){ 26 w += c[i]; 27 if(w>mid){ 28 cnt++; 29 w = c[i]; 30 } 31 } 32 if(cnt>m) low = mid +1; 33 else high = mid -1; 34 } 35 cout<<low<<endl; 36 return 0; 37 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。