POJ-2586 解题报告

先让我吐槽一下…这题的题目真的不愧于“POJ最大的纸老虎”的称号啊!我用有道来来回回看了N遍愣是看不懂…最后百度了一下才知道它到底在说什么…

题意简述

MS公司的财务每月有盈利或赤字两种可能,若盈利则必盈利s元,若亏损则必亏损d元。已知1999年1~5月,2~6月,3~7月……8~12月,每五个月MS公司财务累计均为赤字。问1999年全年MS公司是否可能盈利?若能盈利则输出最大盈利,若不能盈利则输出“Deficit”。输入数据有多组。每行一组。

算法分析

贪心。

易证得全年盈利只与12个月中盈利月总数和亏损月总数相关,与各月具体盈利或亏损无关。

分析可知,欲满足每5个月总和为亏损,全年又必须盈利,则需要令每五个月内的亏损尽可能少。又为了尽可能多的让亏损月份可以在其他区间中共享,令5个月中的亏损月后置,盈利月前置。

1~5月中盈利亏损分部仅有以下几种可能:

ssssd

sssdd

ssddd

sdddd

确定第一个月的分部后,后面月份可以根据【统计亏损月份数量是否足够,不足则在末尾补上】的策略推出。

只需按亏损月数递增的顺序扫描上述四种方案,直到能使5个月总和为亏损则停止。由选定的方案即可确定全年12个月方案。则可求出全年是否盈利。若全年财务为负值则不可盈利。

(因ddddd的情况为全年亏损,明显无法盈利,故不用考虑。若遇到四个月亏损一个月盈利仍无法使5个月总和为负,则直接输出Deficit)

根据前五个月可推出全年方案只有四种:

ssssdssssdss

sssddsssddss

ssdddssdddss

sddddsddddsd

将四种方案的盈利月数和亏损月数总和直接存储在常数组中,方便计算。

程序样例

[c]#include<stdio.h>
int main()
{
const int a[4][2]={3,9,6,6,8,4,10,2};
int s,d,i;
while(scanf("%d%d",&s,&d)==2)
{
for(i=4;i>=1;i–)
if(s*i<d*(5-i)) break;
if (i==0||(s*a[i-1][0]-d*a[i-1][1])<0)
printf("Deficitn");
else
printf("%dn",s*a[i-1][0]-d*a[i-1][1]);
}
return 0;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *