POJ 2586:Y2K Accounting Bug(贪心)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10024 | Accepted: 4990 |
Description
Input
Output
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
题意是:
对于每个月来说,不是盈利,就是亏损,假设是盈利则盈利S,假设亏空则亏d。
每五个月进行一次统计,共统计八次(1-5月一次,2-6月一次.......8-12月一次)
统计的结果是这八次都是亏空。
问题:推断全年能否盈利,假设能则求出最大的盈利。
假设不能盈利则输出Deficit
贪心思想: 每五个连续的月一定亏损,也就是不能出现连续5个月盈利,我们能够设每五个月亏损月数最少为x,这样的情况下, 假设x能保证让这五个月为亏损,这是满足题意的盈利最大值! (比x大的,盈利也少了,题意是让求最大利润),x仅仅能为1,2,3,4,5. 当然x=5时, 则一定亏空。。 除了则之后,也就仅仅有四种情况ssssd ssssd ss sssdd sssdd ss ssddd ssddd ss sdddd sdddd sd
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<sstream> #include<cmath> using namespace std; #define M 100500 int main() { int s, d; while(~scanf("%d%d", &s, &d)) { if(s>4*d) { printf("Deficit\n"); continue; } int t = 1; while(s*(5-t)>d*t) t++; int k; if(t==4) k = 2*t+1; else k = 2*t; int ans = s * (12-k) - d*k; if(ans>0) printf("%d\n", ans); else printf("Deficit\n"); } return 0; }