本文主要是介绍POJ 2586 Y2K Accounting Bug 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：对于MS Inc来说，每个月如果盈利则必盈利sur，如果亏空则必亏空def（这个公司很怪）。它每五个月进行一次统计，共统计八次（1-5月一次，2-6月一次...）。统计的结果是这八次都亏空。判断MS Inc全年否能盈利，如果能则求出最大的盈利。如果不能则输出"Deficit"。
题解：
已知每月盈利为S，亏损为 d。则每个阶段的5个月里要么是 S，剩余的都是 d。
即5个月中， 4个 S 就有 ( 5 - 4 ) 个 d，3个 S 就有( 5 - 3 ) 个 d 依次类推。
这样在保证这样的前提下,尽可能的在5个月中多放入S， 但要保证放入的 max 个 S 的和不能大于 5 - max 个 d 的和。
8个阶段中相邻的阶段都会都相同的四个月的子集，如阶段 1 为 1 - 5 月，阶段 2 为 2 - 6 月，其中的 2 - 5 月就是公共子集。
找到最少每个阶段要放 5 - max 个 d。当然，为了使每次统计尽量共用更多的 d 。那么 5 - max 个 d 应该放在 1 - 5 这个区间的后 5 - max 个位置。
#include <iostream>
using namespace std;
int month[13];
int main()
{
int s, d;
int i, j, cnt, dnum;
while ( cin >> s >> d )
{
memset(month,0,sizeof(month)); /* 全部初始化为0，即假设一开始所有都surplus */
/* 对1,2,3,4,5月进行赋值，1表示deficit,0表示surplus */
dnum = 0;
while ( dnum * d <= (5-dnum)*s && dnum <= 5 )
{
month[5-dnum] = 1;
dnum++; //计算每5个月中至少有多少deficit
}
/* 从第二次统计开始，计算每连续5个月中deficit的个数，若少于dnum个, 就将本次统计的最后一个月设为deficit */
for ( j = 2; j <= 8; j++ )
{
cnt = 0;
for ( i = j; i <= j+4; i++ )
{
if ( month[i] ) cnt++;
if ( i == j + 4 && cnt < dnum ) month[i] = 1;
}
}
cnt = 0;
for ( i = 1; i <= 12; i++ ) //经过前面的处理后，现在可以计算12个月中究竟有多少月份是deficit
if ( month[i] ) cnt++;
if ( d * cnt <= s*(12-cnt) )
cout << s * (12-cnt) - d * cnt << endl;
else
cout << "Deficit" << endl;
}
return 0;
}当然，由于题目的数据量很小，我们可以预先把所有的情况列举出来。
1 .若SSSSD亏空，那么全年可能最大盈利情况为: SSSSDSSSSDSS
2.若SSSDD亏空，那么全年可能最大盈利情况为：SSSDDSSSDDSS
3.若SSDDD亏空，那么全年可能最大盈利情况为: SSDDDSSDDDSS
4.若SDDDD亏空，那么全年可能最大盈利情况为: SDDDDSDDDDSD
5.若DDDDD亏空，那么全年可能最大盈利情况为: DDDDDDDDDDDD
#include <cstdio>
#include <cstdlib>
int main()
{
int s, d, sum, max;
while( scanf("%d%d", &s, &d) != EOF )
{
max = -12 * d;
if (4 * s < d)
{
sum = 10 * s - 2 * d;
if (sum > max) max = sum;
}
else if (3 * s < 2 * d)
{
sum = 8 * s - 4 * d;
if (sum > max) max = sum;
}
else if (2 * s < 3 * d)
{
sum = 6 * s - 6 * d;
if (sum > max) max = sum;
}
else if (s < 4 * d)
{
sum = 3 * s - 9 * d;
if (sum > max) max = sum;
}
if (max > 0)
{
printf("%d\n", max);
}
else
{
printf("Deficit\n");
}
}
return 0;
}
这篇关于POJ 2586 Y2K Accounting Bug 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
