首页 > 代码库 > 【bzoj1572-工作安排】贪心

【bzoj1572-工作安排】贪心

2024-08-18 00:44:33   220人阅读

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1572

题意：

约翰接到了N份工作，每份工作恰好占用一天的时间。约翰从第一天开始工作，他可以任意安排这些工作的顺序，第i份工作有Pi的报酬，但必须在第Di天结束之前完成。问最多能赚多少钱。n<=10^5,di,pi<=10^9

题解：

贪心。按di排序，如果天数不够就把pi最小的放弃。具体来说就是di从小到大扫一遍，如果pi>0就把它放进优先队列（按pi排序）里，如果q.size()>di也就是天数不够做完这些工作，就把队头也就是最小的pi pop出来。

 

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 #include<set>
 9 using namespace std;
10 
11 typedef long long LL;
12 const int N=100010;
13 int n;
14 struct node{
15     int d;LL p;
16 }a[N];
17 struct cmp{
18     bool operator() (int &x,int &y)
19     {
20         return a[x].p>a[y].p;
21     }
22 };
23 priority_queue<int,vector<int>,cmp> q;
24 
25 bool cmp(node x,node y){return x.d<y.d;}
26 
27 int main()
28 {
29     // freopen("a.in","r",stdin);
30     freopen("job.in","r",stdin);
31     freopen("job.out","w",stdout);
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++)
34     {
35         scanf("%d%d",&a[i].d,&a[i].p);
36     }
37     sort(a+1,a+1+n,cmp);
38     while(!q.empty()) q.pop();
39     int x;
40     LL ans=0;
41     for(int i=1;i<=n;i++)
42     {
43         if(a[i].p>0) 
44         {
45             q.push(i);
46             ans+=a[i].p;
47         }
48         while(q.size()>a[i].d) 
49         {
50             x=q.top();
51             ans-=a[x].p;
52             q.pop();
53         }
54     }
55     printf("%lld\n",ans);
56     return 0;
57 }

 

【bzoj1572-工作安排】贪心


联系
我们