Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-2586 解题报告

POJ

先让我吐槽一下…这题的题目真的不愧于“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

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

程序样例

#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("Deficit\n");
    else
      printf("%d\n", s * a[i - 1][0] - d * a[i - 1][1]);
  }
  return 0;
}

Leave a Reply

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