首页 > 代码库 > bzoj1572[Usaco2009 Open]工作安排Job
bzoj1572[Usaco2009 Open]工作安排Job
bzoj1572[Usaco2009 Open]工作安排Job
题意：
n个工作，每个需要的时间都为1，最晚完成时间为ti，价值为vi，问最多能得到的价值。n≤100000。
题解：
先把所有工作按最晚开始时间排序，然后把能做的工作先做掉（如果前面的工作时间有空隙可以填上），处理剩下的工作时，比较之前做的工作中价值最小的工作的价值和当前工作的价值，如果之前做的工作价值更小就把它踢掉，换成当前工作。这一过程用优先队列维护。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 #define ll long long 8 using namespace std; 9 10 inline ll read(){11 char ch=getchar(); ll f=1,x=0;12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14 return f*x;15 }16 struct nd{ll t,v; bool operator < (const nd &a)const{return v>a.v;}}nds[maxn]; priority_queue<nd>q;17 bool cmp(nd a,nd b){return a.t<b.t;} int n; ll ans,tot;18 int main(){19 n=read(); inc(i,1,n){ll x=read(); ll y=read(); nds[i]=(nd){x-1,y};} sort(nds+1,nds+1+n,cmp);20 inc(i,1,n){21 if(tot<=nds[i].t)q.push(nds[i]),ans+=nds[i].v,tot++;else{22 ll a=q.top().v; if(a<nds[i].v)q.pop(),q.push(nds[i]),ans-=a,ans+=nds[i].v;23 }24 }25 printf("%lld",ans); return 0;26 }
20160918
bzoj1572[Usaco2009 Open]工作安排Job
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。