首页 > 其他 > 详细

BZOJ 1572 工作安排

时间:2017-10-19 15:30:26      阅读:247      评论:0      收藏:0      [点我收藏+]

技术分享

技术分享

先把工作按照Deadline从小到大排序

然后按顺序取,deadline大于现在总用时就取,等于现在总用时就从前面已取的工作中找一个P最小的同它比较,取P较大的一个

用优先队列维护已取工作中P的最小值

技术分享
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #define LL long long
 5 using namespace std;
 6 const int maxn=100010;
 7 LL n,ans=0,t=0;
 8 struct work{
 9     LL d,p;
10 }a[maxn];
11 struct cmp1{
12     bool operator() (const LL a,const LL b)const {return a>b;}
13 };
14 priority_queue<int,vector<int>,cmp1>q;
15 void read(long long &k){
16     int f=1; k=0; char c=getchar();
17     while (c<0||c>9)c==-&&(f=-1),c=getchar();
18     while (0<=c&&c<=9)k=k*10+c-0,c=getchar();
19     k*=f;
20 }
21 bool cmp2(work a,work b){return a.d<b.d;}
22 int main(){
23     read(n);
24     for (int i=1;i<=n;i++) read(a[i].d),read(a[i].p);
25     sort(a+1,a+n+1,cmp2);
26     for (int i=1;i<=n;i++){
27         if (a[i].d>t) q.push(a[i].p),ans+=a[i].p,t++;
28         else{
29             int x=q.top(); 
30             if (x<a[i].p){
31                 q.pop(); q.push(a[i].p);
32                 ans+=a[i].p-x;
33             }
34         }
35     }
36     printf("%lld\n",ans);
37     return 0;
38 }
View Code

 

BZOJ 1572 工作安排

原文:http://www.cnblogs.com/DriverLao/p/7692565.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!