1572: [Usaco2009 Open]工作安排Job
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 775 Solved: 337
[Submit][Status]
Description
Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。 他的工作日从0时刻开始,有1000000000个单位时间(!)。在任一时刻,他都可以选择编号1~N的N(1 <= N <= 100000)项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有N个工作,虽然还是有可能。 对于第i个工作,有一个截止时间D_i(1 <= D_i <= 1000000000),如果他可以完成这个工作,那么他可以获利P_i( 1<=P_i<=1000000000 ). 在给定的工作利润和截止时间下,FJ能够获得的利润最大为多少呢?答案可能会超过32位整型。
Input
第1行:一个整数N. 第2~N+1行:第i+1行有两个用空格分开的整数:D_i和P_i.
Output
输出一行,里面有一个整数,表示最大获利值。
Sample Input
2 10
1 5
1 7
Sample Output
HINT
第1个单位时间完成第3个工作(1,7),然后在第2个单位时间完成第1个工作(2,10)以达到最大利润
Source
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#define inf 1000000000
#define maxn 100000+1000
#define maxm 500+100
#define eps 1e-10
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
priority_queue<int,vector<int> >q;
struct rec{int x,y;}a[maxn];
bool cmp(rec a,rec b)
{
return a.x<b.x;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n=read();
for(int i=;i<=n;i++)
{
a[i].x=read();a[i].y=read();
}
sort(a+,a+n+,cmp);
//for(int i=1;i<=n;i++)cout<<i<<' '<<a[i].x<<' '<<a[i].y<<endl;
int time=inf,i=n;ll ans=;
while(time)
{
while(a[i].x<time)
{
if(q.empty())time=a[i].x;
else
{
ans+=q.top();q.pop();time--;
//cout<<ans<<' '<<q.top()<<' '<<a[i].x<<' '<<i<<endl;
}
}
q.push(a[i].y);
while(a[i].x==a[i-].x)q.push(a[--i].y);
i--;
}
printf("%lld\n",ans);
return ;
}
竟然在bzoj上rank3了,原来以为我在status里面总是排老后面的原因是我的算法不够优,现在才发现是语言的问题2333。。。
BZOJ1572: [Usaco2009 Open]工作安排Job的更多相关文章
-
[bzoj1572][Usaco2009 Open]工作安排Job_贪心_堆
工作安排 Job bzoj-1572 Usaco-2009 Open 题目大意:题目链接. 注释:略. 想法: 我们将任务按照截止时间排序,枚举任务的同时顺便记录出已经做了多少任务(当前时间). 对于 ...
-
【贪心】bzoj1572: [Usaco2009 Open]工作安排Job
先是没怎么理解这个贪心……然后贪心又被细节弄挂…… Description Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间. ...
-
[BZOJ1572] [Usaco2009 Open]工作安排Job(贪心 + 堆)
传送门 把任务按照d排序 一次加入到堆中,如果当前放不进堆中,并且比堆中最小的大, 就从堆中弹出一个数,再把当前的数放进去 #include <queue> #include <cs ...
-
bzoj1572 [Usaco2009 Open]工作安排Job【贪心 堆】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1572 尽管这一题没有看题解,但是耗时还是比本应耗费的时间要长,所以还是写一下,以提升经验 这 ...
-
BZOJ 1572: [Usaco2009 Open]工作安排Job( 贪心 )
贪心... 按截止时间排序 , 然后从小到大考虑 . 假设当前考虑第 i 个任务 , 若目前已选工作数 < D_i , 那就选 i ; 否则 若已选工作中利润最小的比 P_i 小 , 那就去除它 ...
-
【BZOJ 1572】 1572: [Usaco2009 Open]工作安排Job(贪心+优先队列)
1572: [Usaco2009 Open]工作安排Job Description Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单 ...
-
1572: [Usaco2009 Open]工作安排Job
1572: [Usaco2009 Open]工作安排Job Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 814 Solved: 365[Submit ...
-
【bzoj1572】[Usaco2009 Open]工作安排Job 贪心+堆
题目描述 Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间. 他的工作日从0时刻开始,有1000000000个单位时间(!). ...
-
1572: [Usaco2009 Open]工作安排Job[贪心]
Description Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间. 他的工作日从0时刻开始,有1000000000个单 ...
随机推荐
- git常用功能
-
asp.net webapi [FromBody]string 获取不到ajax post的数据的解决方法
webapi中如下([FromBody]string jsonData: public async Task<ResItem> Post([FromBody]string jsonData ...
-
LR动态脚本的处理
在处理SSO修改密码脚本时遇到一个问题,根据用户名的不同,提交请求中数据会不一样.处理此问题,如果经分析用同类型的账号(每个账号含有的子账号类型和数目一致)测试与实际不同类型账号性能没有大的差别,则用 ...
-
Sql Server REPLACE函数的使用;SQL中 patindex函数的用法
Sql Server REPLACE函数的使用 REPLACE用第三个表达式替换第一个字符串表达式中出现的所有第二个给定字符串表达式. 语法REPLACE ( ''string_replace1'' ...
-
Analyzer使用第二Y轴,以及同一分析图不同量值使用不同的图形样式
Analyzer的建立分析图后,图中有两个量值,希望能显示成不同的图形样式,如一个是柱图.一个是线图. 1.设置显示多个量值: 3.设置显示出图例,即表明图中量值内容的说明: 2.右键图例中要修改为不 ...
-
站在巨人的肩膀上学习Android开发
我们知道,一開始最好的学习方法是模仿,尤其是模仿巨人. 那说到Android开发的模仿自然就是分析并研究主流程序的布局.实现方法.进而提升自己的技术. 第一招----逆向project 要分析&quo ...
-
Mysql入门到精通数据表的操作
变更表 ALTER TABLE tb_name; 1.加入场 ALTER TABLE tb_name ADD 字段名字 字段类型 约束条件 [FIRST/AFTER 字段名称] 1>加入user ...
-
【NOIP模拟】table(动态规划)
题目背景 SOURCE:NOIP2016-RZZ-2 T2 题目描述 给定一个 n×m 的矩阵,行列均从 1 开始标号. 一个矩阵被认为是稳定的,当且仅当对于任意的 2≤i≤n,第 i 行的数的和不小 ...
-
[Swift]LeetCode312. 戳气球 | Burst Balloons
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by ...
-
.Net三层架构
.Net三层架构 希望朋友们留下自己对三层架构的理解... 三层体系结构的概念 用户界面表示层(USL) 业务逻辑层(BLL) 数据访问层(DAL) BLL将USL与DAL隔开了,并且加入了业务规 ...