POJ 2586-Y2K Accounting Bug Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10647 Accepted: 5328 Description Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite. Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post. Input Input is a sequence of lines, each containing two positive integers s and d. Output For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible. Sample Input 59 237 375 743 200000 849694 2500000 8000000 Sample Output 116 28 300612 Deficit Source Waterloo local 2000.01.29
这个题首先要读懂题意，其中的
ACM knows that each of these 8 postings reported a deficit我一开始看不懂，不知道这个8代表什么意思，是怎么来的，看过别人的解释才知道，原来前面说每连续5个月会发布一次盈亏报告，而一年又12个月，总共可以发布8次，即：1-5,2-6,3-7,4-8,5-9,6-10,7-11,8-12。注意每次报告的月份和前后的报告的月份是有重叠的。 题目告诉我们这8次报告都是亏损，但是求这一年是否可以盈利，总的盈利最多是多少。这道题有点最优化的感觉，已知约束是8次报告都是亏损，求最优化总的盈利。 这道题可以有两种解法。 贪心 因为要求盈利最大化，所以可以先设12个月都是盈利的，然后再慢慢调整满足8次报告都是亏损的。一次报告是连续的5个月的总和，要保证一次报告是亏损，5个月里至少一个月是亏损的，亏损的月份放在5个月里的最后月份是最好的，因为这样可以和下一个报告重叠，使总的盈利最大。比如1-5使第5月份亏损，就能保证这个报告亏损，则2-6已经包含5月份了，当然这个报告肯定也亏损。这样1-5和2-6实际只有5月份是亏损的。但是如果1-5使第1月份亏损，虽然第一个报告是亏损的，但是2-6还是盈利的，又使第2月份亏损，则1-5和2-6实际有1月份和2月份是亏损的，这就亏损了两个月。 所以每次我们要亏损时，都从该报告的最后月份开始试探，一直往前试探，直到这个报告亏损。一直循环8个报告。最后求这一年总的盈亏。代码如下： [cpp] #include<iostream> #include<vector> using namespace std; int main() { int s,d; while(cin>>s>>d) { int surplus_num;//盈余的月份数 vector<int> month(12,1);//初始的时候每个月都是surplus，1为surplus，0为deficit for(int i=0;i<8;i++)//8个‘连续5个月’ { surplus_num=0; for(int j=0;j<5;j++) surplus_num+=month[i+j]; int k=0; while(surplus_num*s>=(5-surplus_num)*d) { month[i+4-k]=0;//亏损的月份尽量放到后面，因为可以和下一个周期重叠，这样总的surplus会大一些 surplus_num=0; for(int j=0;j<5;j++) surplus_num+=month[i+j]; k++; } } surplus_num=0; for(int i=0;i<12;i++) surplus_num+=month[i]; int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏 if(rs<0) cout<<"Deficit"<<endl; else cout<<rs<<endl; } return 0; } [/cpp] 这个版本提交AC，用时32MS，内存216K。 枚举 因为这题只有12月份，每个报告只是连续5个月，要是每个报告都亏损，则可以在5个月里有1个月份亏损、2个月份亏损、3个月份亏损、4个月份亏损、5个月份亏损。前4种情况依次求解，直到既满足每个报告亏损，又使12个月总的是盈利。如果前4种都不行，那总的肯定是亏损。 这4种情况可以这样来表示，由于每5个月的报账都为亏损，所有连续的5个月里至少有1个月为亏损，则可能产生最优解的情况为如下4种
1 2 3 4 5 6 7 8 9 10 11 12 s s s s d s s s s d s s //每5个月里只有1个月亏损 s s s d d s s s d d s s //每5个月里只有2个月亏损 s s d d d s s d d d s s //每5个月里只有3个月亏损 s d d d d s d d d d s d //每5个月里只有4个月亏损从上到下一次枚举四种情况，如果满足条件（每次报账都为亏损），则算出ans = (盈利的月数)*s – (亏损的月数)*d,若ans>0 则输出 否则输出Deficit；若上述4种情况都不满足，则直接输出Deficit. 代码如下： [cpp] #include<iostream> using namespace std; int main() { int a,b; while(cin>>a>>b) { int ans = 0; if(4*a-b<0) { ans = 10*a-2*b; } else if(3*a-2*b<0) { ans = 8*a-4*b; } else if(2*a-3*b<0) { ans = 6*a-6*b; } else if(a-4*b<0) { ans = 3*a-9*b; } else { ans = -1; } if(ans>0) cout<<ans<<endl; else cout<<"Deficit"<<endl; } return 0; } [/cpp] 这个版本提交AC，用时0MS，内存216K。 很显然，枚举速度更快，但是如果总共有1000个月份，每个报告20个月，共50个报告，或者数字更大时，枚举就很麻烦了，所以掌握第一种贪心的方法还是很有必要的。]]>