【贪心】POJ 2586:Y2K Accounting Bug

    科技2022-07-10  142

    一、题目内容

    POJ 2586 原题地址

    二、题意解释

    某公司每个月要么盈利s元,要么亏损d元, 一年之中任意连续的五个月的利润和是亏损的,最后问一年的总收入是多少, 如果盈利即输出数额,如果亏损,则输出Deficit。

    三、代码及注释

    #include<cstdio> using namespace std; /* 贪心,要使每五个月都亏损,那么就让这些亏损的月份在后面更有利 符合最优子结构性质。5个月统计一次都亏空,那么有5种情况: 1、若SSSSD亏空,那么全年可能最大盈利情况为: SSSSDSSSSDSS 2、若SSSDD亏空,那么全年可能最大盈利情况为:SSSDDSSSDDSS 3、若SSDDD亏空,那么全年可能最大盈利情况为: SSDDDSSDDDSS 4、若SDDDD亏空,那么全年可能最大盈利情况为: SDDDDSDDDDSD 5、若DDDDD亏空,那么全年可能最大盈利情况为: DDDDDDDDDDDD */ int main() { int s, d; while(scanf("%d%d", &s, &d) != EOF) { int k=0; for(k=1; k<=5; k++) { if(k*d > s*(5-k)) break; } k = 5-k;//k此时为每5个月s的数量 if(k == 1) k = 3; else if(k > 1) k = 2*k+2;//这是根据列出的格式决定的总体s的数量 if(s*k - d*(12-k) > 0) printf("%d\n", s*k - d*(12-k)); else printf("Deficit\n"); } return 0; }
    Processed: 0.012, SQL: 8