「BZOJ1572」[Usaco2009 Open] 工作安排Job
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
3
2 10
1 5
1 7
2 10
1 5
1 7
Sample Output
17
HINT
第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润
题解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int n,last,sz; ll ans; struct data{int d,p;}a[100001],hp[100001]; bool cmp(data a,data b){return a.d<b.d;} void put(data x) { ans+=x.p; hp[++sz]=x; int now=sz; while(now>1&&hp[now].p<hp[now>>1].p) { swap(hp[now],hp[now>>1]); now>>=1; } } void pop() { ans-=hp[1].p; hp[1]=hp[sz--]; int next,now=1; while(now<=(sz>>1)) { next=(now<<1); if(next<sz&&hp[next].p>hp[next|1].p)next++; if(hp[now].p<hp[next].p)return; swap(hp[now],hp[next]); now=next; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].d,&a[i].p); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { put(a[i]);last++; if(last>a[i].d){pop();last--;} } printf("%lld",ans); return 0; } |
Subscribe
计数器 9787690
OI 课件=>
OI 课件=>