POJ 2586 - Y2K Accounting Bug


问题描述

无。

解题思路

见代码注释。

AC 源码

Download Link

/*
    Author:     Exp
    Date:       2017-12-25
    Code:       POJ 2586
    Problem:    Y2K Accounting Bug
    URL:        http://poj.org/problem?id=2586
*/

/*
    题意分析:
     已知一个公司在某一年中,【每个月要么固定盈利s、要么固定亏损d】。
     但是具体哪个月盈利、那个月亏损却不得而知。
     不过可以肯定的是,这一年中,【任意的连续5个月盈亏和必定是亏损(< 0)】。
     问这年是否存在盈利的可能,若可能盈利,【最大的盈利额】是多少?


    解题思路:
      要求全年最大盈利额,最理想的情况是每月盈利,即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 <iostream>
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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1129 - Channel Allocation POJ 1129 - Channel Allocation
POJ 1129 - Channel Allocation Time: 1000MS Memory: 10000K 难度: 初级 分类: 搜索 问题描述当一个广播电台在一个非常大的地区,广播站会用中继器来转播信号以使得每一个接收器都能接
2011-02-12
下一篇 
POJ 2299 - Ultra-QuickSort POJ 2299 - Ultra-QuickSort
POJ 2299 - Ultra-QuickSort Time: 1000MS Memory: 65536K 难度: 初级 分类: 排序 问题描述给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。
2011-02-06
  目录