POJ3273-Monthly Expense

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1301655498

 

大致题意:

给出农夫在n天中每天的花费,要求把这n天分作m组,每组的天数必然是连续的,要求分得各组的花费之和应该尽可能地小,最后输出各组花费之和中的最大值

 

解题思路:

经典的二分穷举

详细的思路我写在程序注释中,这样会更容易懂

看完我的程序还是无法切入题目的同学,建议先用 朴素的穷举 去左这题,虽然很大机会会超时,但是只是为了辅助理解。本题的二分纯粹是一个优化穷举的工具。

 1 //Memory Time 
2 //612K 297MS
3
4 #include<iostream>
5 using namespace std;
6
7 int n; //天数
8 int m; //规定的分组数
9
10 /*判断用当前的mid值能把天数n分成几组*/
11 /*通过比较group与m的大小,对mid值进行优化*/
12
13 bool judge_group(int mid,int money[])
14 {
15 int sum=0;
16 int group=1; //当前mid值能把n天分成的组数(初始把全部天数作为1组)
17
18 for(int i=1;i<=n;i++) //从第一天开始向下遍历每天的花费
19 if(sum+money[i]<=mid) //当前i天之和<=mid时,把他们归并到一组
20 sum+=money[i];
21 else //若 前i-1天之和 加上第i天的花费 大于mid
22 {
23 sum=money[i]; //则把前i-1天作为一组,第i天作为下一组的第一天
24 group++; //此时划分的组数+1
25 }
26
27 if(group>m)
28 return false; //若利用mid值划分的组数比规定的组数要多,则说明mid值偏小
29 else
30 return true; //否则mid值偏大
31 }
32
33 int main(void)
34 {
35 while(cin>>n>>m)
36 {
37 int* money=new int[n+1]; //每天花费的金额
38 int low=0; //下界
39 int high=0; //上界
40
41 for(int i=1;i<=n;i++)
42 {
43 cin>>money[i];
44
45 high+=money[i]; //把所有天数的总花费作为上界high(相当于把n天都分作1组)
46 if(low<money[i])
47 low=money[i]; //把n天中花费最多的那一天的花费作为下界low(相当于把n天分为n组)
48 } //那么要求的值必然在[low,high]范围内
49
50 int mid=(low+high)/2;
51
52 while(low<high) //可能在low==high之前,分组数就已经=m,但是mid并不是最优,因此要继续二分
53 {
54 if(!judge_group(mid,money))
55 low=mid+1; //mid值偏小,下界前移
56 else
57 high=mid-1; //mid值偏大,上界后移
58
59 mid=(low+high)/2;
60 }
61
62 cout<<mid<<endl; //二分搜索最后得到的mid值必然是使得分组符合要求的最优值
63
64 delete money;
65 }
66 return 0;
67 }

我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top