本文共 2860 字，大约阅读时间需要 9 分钟。

Y2K Accounting Bug

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 17533		Accepted: 8875

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 237375 743200000 8496942500000 8000000

Sample Output

11628300612Deficit

Source

大致题意：

1. 已知一个公司在某一年中，【每个月要么固定盈利s、要么固定亏损d】。

2. 但是具体哪个月盈利、那个月亏损却不得而知。

3. 不过可以肯定的是，这一年中，【任意的连续5个月盈亏和必定是亏损（< 0）】。

4. 问这年是否存在盈利的可能，若可能盈利，【最大的盈利额】是多少

解题思路：

      要求全年最大盈利额，最理想的情况是每月盈利，即12s       但这里有个大前提：【任意的连续5个月盈亏和必定是亏损】              因此这题可用贪心法去求解：         从1月份开始，选择当月是盈或亏，但尽可能选择为盈利，           当且仅当无法满足【连续5月必亏损】这个条件时，当月才选择亏损       由于组合情况较少，可以把每5个月的所有盈亏组合情况列举出来：       ① 当 s >= 4d 时 （即1个月的盈利抵得上4个月的亏损），           无论如何组合，都无法满足【连续5月必亏损】的前提，           因此为了满足这种情况，只可能所有月份均亏损           即亏损月份为 [1-12]           全年无利润       ② 当 s < 4d （但2s >= 3d） 时 （即1个月的盈利刚好小于4个月的亏损）,           此时只需保证每连续5个月至少有4个月是亏损即可，           根据贪心逻辑，全年盈亏月份为：sddddsddddsd           即盈利月份为 1、6、11             亏损月份为 [2-5]、[7-10]、12           全年最大利润为: 3s - 9d       ③ 当 2s < 3d （但3s >= 2d）时 （即2个月的盈利刚好小于3个月的亏损）,           此时只需保证每连续5个月至少有3个月是亏损即可，           根据贪心逻辑，全年盈亏月份为：ssdddssdddss           即盈利月份为 [1-2]、[6-7]、[11-12]             亏损月份为 [3-5]、[8-10]           全年最大利润为: 6s - 6d       ④ 当 3s < 2d （但4s >= d）时 （即3个月的盈利刚好小于2个月的亏损）,           此时只需保证每连续5个月至少有2个月是亏损即可，           根据贪心逻辑，全年盈亏月份为：sssddsssddss           即盈利月份为 [1-3]、[6-8]、[11-12]             亏损月份为 [4-5]、[9-10]           全年最大利润为: 8s - 4d       ⑤ 当 4s < d 时 （即4个月的盈利刚好小于1个月的亏损）,           此时只需保证每连续5个月至少有1个月是亏损即可，           根据贪心逻辑，全年盈亏月份为：ssssdssssdss           即盈利月份为 [1,4]、[6-9]、[11-12]             亏损月份为 5、10           全年最大利润为: 10s - 2d

代码：

#include 
   
    using namespace std; int main(void) {	int s, d;	while(cin >> s >> d) { 		int surplus = 0;	// 全年盈余		if(4 * s < d) {			surplus = 10 * s - 2 * d;					} else if(3 * s < 2 * d) {			surplus = 8 * s - 4 * d; 		} else if(2 * s < 3 * d) {			surplus = 6 * s - 6 * d; 		} else if(s < 4 * d) {			surplus = 3 * s - 9 * d; 		} else {			surplus = -1;		} 		if(surplus < 0) {			cout << "Deficit" << endl;		} else {			cout << surplus << endl;		}	}	return 0;}
   

 

转载地址：https://joycez.blog.csdn.net/article/details/82779475 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！