题目地址: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;
}
*/
贪心 POJ 2586 Y2K Accounting Bug的更多相关文章
-
poj 2586 Y2K Accounting Bug (贪心)
Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8678 Accepted: 428 ...
-
POJ 2586 Y2K Accounting Bug 贪心 难度:2
Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10537 Accepted: 52 ...
-
poj 2586 Y2K Accounting Bug
http://poj.org/problem?id=2586 大意是一个公司在12个月中,或固定盈余s,或固定亏损d. 但记不得哪些月盈余,哪些月亏损,只能记得连续5个月的代数和总是亏损(<0为 ...
-
POJ 2586 Y2K Accounting Bug(枚举洪水问题)
Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10674 Accepted: 53 ...
-
POJ 2586 Y2K Accounting Bug(枚举大水题)
Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10674 Accepted: 53 ...
-
[POJ 2586] Y2K Accounting Bug (贪心)
题目链接:http://poj.org/problem?id=2586 题目大意:(真难读懂啊)给你两个数,s,d,意思是MS公司每个月可能赚钱,也可能赔钱,如果赚钱的话,就是赚s元,如果赔钱的话,就 ...
-
POJ 2586 Y2K Accounting Bug(贪心)
题目连接:http://poj.org/problem?id=2586 题意:次(1-5.2-6.3-7.4-8.5-9.6-10.7-11.8-12),次统计的结果全部是亏空(盈利-亏空<0) ...
-
poj 2586 Y2K Accounting Bug(贪心算法,水题一枚)
#include <iostream> using namespace std; /*248K 32MS*/ int main() { int s,d; while(cin>> ...
-
POJ - 2586 Y2K Accounting Bug (找规律)
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for ...
随机推荐
-
Java 中使用javah编译头文件出现找不到类的情况
在工程的bin目录下,输入命令: javah -classpath . -jni 类路径.JNI类
-
Android入门(七):Spinner下拉式菜单组件
对于手机和平板电脑的应用程序来说,打字是非常不方便的操作方式,比较好的方式就是列出一组选项让用户挑选,这样就可以避免打字的麻烦.使用Spinner下拉菜单组件需要完成以下几个步骤: 1.建立选项列表, ...
-
jQuery原生框架-----------------dom操作
// 扩展DOM操作方法jQuery.fn.extend({ // 设置或者获取元素的内容 html: function( html ) { /* * 实现思路: * 1.不传参,返回第一个元素的内容 ...
-
图算法(一)——基本图算法(BFS,DFS及其应用)(1)
1)BFS 广度优先搜索:给定源节点s,生成广度优先搜索树广度优先搜索树中从节点s到节点v的简单路径对应的就是s到v的最短路径(边数最少的路径)广度优先:将已发现节点与未发现节点之间的边界(灰色节点) ...
-
Python基础教程【读书笔记】 - 2016/8/3
希望通过博客园持续的更新,分享和记录Python基础知识到高级应用的点点滴滴! 第十一波:第11章 文件和素材 本章更进一步,让程序能够接触更多的领域:文件和流.接下来介绍的函数和对象可以让你在程序 ...
-
【UVALive - 3713】Astronauts (2-SAT)
题意: 有n个宇航员,按照年龄划分,年龄低于平均年龄的是年轻宇航员,而年龄大于等于平均年龄的是老练的宇航员. 现在要分配他们去A,B,C三个空间站,其中A站只有老练的宇航员才能去,而B站是只有年轻的才 ...
-
Scrapy中使用cookie免于验证登录和模拟登录
Scrapy中使用cookie免于验证登录和模拟登录 引言 python爬虫我认为最困难的问题一个是ip代理,另外一个就是模拟登录了,更操蛋的就是模拟登录了之后还有验证码,真的是不让人省心,不过既然有 ...
-
Mac系统下XAMPP的简单使用
XAMPP简单使用的方法使用方法 XAMPP的简介即应用在博客园也有 1.安装完成后打开manager-osx.app 把Manager Servers下的三个server打开(使之变绿如下) 第一个 ...
-
Shell test 命令
Shell中的 test 命令用于检查某个条件是否成立,它可以进行数值.字符和文件三个方面的测试. 数值测试 参数 说明 -eq 等于则为真 -ne 不等于则为真 -gt 大于则为真 -ge 大于等于 ...
-
数据结构与算法之PHP查找算法(二分查找)
二分查找又称折半查找,只对有序的数组有效. 优点是比较次数少,查找速度快,平均性能好,占用系统内存较少: 缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序 ...