贪心 POJ 2586 Y2K Accounting Bug

题目地址:http://poj.org/problem?id=2586

 /*
题意:某公司要统计全年盈利状况,对于每一个月来说,如果盈利则盈利S,如果亏空则亏空D。
公司每五个月进行一次统计,全年共统计8次(1-5、2-6、3-7、4-8、5-9、6-10、7-11、8-12),
已知这8次统计的结果全部是亏空(盈利-亏空<0)。题目给出S和D,判断全年是否能盈利,
如果能则求出盈利的最大值,如果不能盈利则输出Deficit
贪心 or 枚举
1. 贪心抓住亏损的月尽量在5个月的后面,这样可以被下一次利用,从而获取最大值
2. 可以枚举是因为可能的情况少
详细解释:http://blog.csdn.net/lyy289065406/article/details/6642603
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
int used[]; void work(int s, int d)
{
int sum = ; int cnt; int k; cnt = ;
while (s * (cnt) - d * ( - cnt) > && cnt > ) cnt--;
k = - cnt;
sum += s * ( - k) - d * k;
for (int i=; i>= && k--; --i) used[i] = ; for (int i=; i<=; ++i)
{
int n = ;
for (int j=i; j<=+i-; ++j)
{
if (used[j]) n++;
}
int tmp = ;
tmp += s * ( - n) - d * n;
if (tmp < && tmp + s < ) sum += s;
else
{
sum -= d; used[i+] = ;
}
} (sum >= ) ? printf ("%d\n", sum) : puts ("Deficit");
} int main(void) //POJ 2586 Y2K Accounting Bug
{
//freopen ("E.in", "r", stdin); int s, d;
while (~scanf ("%d%d", &s, &d))
{
memset (used, , sizeof (used));
work (s, d);
} return ;
} /*
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; int main(void)
{
//freopen ("E.in", "r", stdin); int s, d;
while (~scanf ("%d%d", &s, &d))
{
int ans = 0;
if (4 * s - d < 0)
{
ans = 10 * s - 2 * d;
}
else if (3 * s - 2 * d < 0)
{
ans = 8 * s - 4 * d;
}
else if (2 * s - 3 * d < 0)
{
ans = 6 * s - 6 * d;
}
else if (1 * s - 4 * d < 0)
{
ans = 3 * s - 9 * d;
}
else ans = -1;
if (ans > 0) printf ("%d\n", ans);
else puts ("Deficit");
} return 0;
}
*/
上一篇:【kd-tree】bzoj2850 巧克力王国


下一篇:Hessian 原理分析--转