首页 > 代码库 > bzoj1029: [JSOI2007]建筑抢修
bzoj1029: [JSOI2007]建筑抢修
usaco做过的贪心题啊。。。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queue>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)){ if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;} const int nmax=150005;struct node{ ll c,t; bool operator<(const node&rhs)const{ return t<rhs.t;}};node ns[nmax];priority_queue<ll>q;int main(){ ll n=read(); rep(i,1,n) ns[i].c=read(),ns[i].t=read(); sort(ns+1,ns+n+1); //rep(i,1,n) printf("%lld %lld\n",ns[i].c,ns[i].t); ll cur=ns[1].c;q.push(ns[1].c);int ans=1; rep(i,2,n){ if(cur+ns[i].c<=ns[i].t){ cur+=ns[i].c;q.push(ns[i].c);ans++; continue; } ll tmp=q.top(); if(tmp>ns[i].c&&cur-tmp+ns[i].c<=ns[i].t){ cur=cur-tmp+ns[i].c;q.pop();q.push(ns[i].c); } } printf("%d\n",ans); return 0;}
1029: [JSOI2007]建筑抢修
Time Limit: 4 Sec Memory Limit: 162 MBSubmit: 3693 Solved: 1705
[Submit][Status][Discuss]
Description
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有z部落的
入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全
毁坏。现在的情况是:T部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需
要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一
段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多
的建筑。
Input
第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑:修理这个建筑需要T1秒,如果在T2秒之内还
没有修理完成,这个建筑就报废了。
Output
输出一个整数S,表示最多可以抢修S个建筑.N < 150,000; T1 < T2 < maxlongint
Sample Input
4
100 200
200 1300
1000 1250
2000 3200
100 200
200 1300
1000 1250
2000 3200
Sample Output
3
HINT
Source
bzoj1029: [JSOI2007]建筑抢修
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。