首页 > 代码库 > POJ 3273
POJ 3273
【题意描述】
给定一串数据,划分成m段,并把每段内的数据相加,使得m段数据中的最大值最小。
【思路分析】
这里很多人可能考虑用DP,但是会超时。那么根据DP与分治的联系,我们可以联想到运用二分法,对所求最大值进行二分,直到所划分区间的数目等于m段即停止。
这里在确定二分的区间有点技巧,首先low肯定是整个数据的最大值,up是整组数据之和,然后进行逐步二分。不断扩大数据值,使得划分的段数不断减小。
【AC代码】
1 #include<iostream> 2 using namespace std; 3 #define max 100005 4 int day_cost[max]; 5 int main() 6 { 7 int n,m; 8 while(cin>>n>>m) 9 {10 int low=0,up=0;11 for(int i=0;i<n;i++)12 {13 cin>>day_cost[i] ;14 up+=day_cost[i];//寻找二分区间的右端15 if(low<day_cost[i])16 low=day_cost[i];//寻找二分区间的左端点17 }18 int mid;19 while(low<up)//二分条件 20 {21 mid=(low+up)/2;22 int sum1=0,num=0;23 for(int i=0;i<n;i++)24 {25 if(sum1+day_cost[i]>mid) 26 {num++;27 sum1=day_cost[i];28 }29 else sum1+=day_cost[i];30 }31 num++;32 if(num>m) low=mid+1;//一定加1,否则死循环,造成时间超限!!!33 else up=mid;34 }35 int low_cost=low;//最后的结果是等于最左端数据的36 cout<<low_cost<<endl;37 }38 return 0;39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。