Work Scheduling（带反悔的贪心）

65 阅读 0 评论 43 点赞

我是靠谱客的博主火星上期待，最近开发中收集的这篇文章主要介绍Work Scheduling（带反悔的贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://www.luogu.org/problem/P2949

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.
His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs conveniently numbered 1..N for work to do. It is possible but extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.
Job i has deadline Di (1 <= Di <= 1,000,000,000). If he finishes job i by then, he makes a profit of Pi (1 <= Pi <= 1,000,000,000).
What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: Di and Pi

输出描述:

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

输入

输出

说明

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

每件物品代价相同，但价值不同。那么我们很容易想到，在满足限制的情况下，我们肯定会选择价值尽可能大的物品。

我们可否用背包来实现呢，答案是否定的，或者说我不会QwQ

那么，我们来看看贪心

首先思路就是先按时间排序（不是那个1e8啊，是截止日期），然后如果一个工作有时间去做，就先做了它（听起来有点怪），然后把它的价值压入一个小根堆。

当我们找到一个没法做却价值比当前堆顶高的工作时，我们就放弃那个最小的工作，用做它的时间去做这个价值更高的工作。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <set>
 9 #include <math.h>
10 const int INF=0x3f3f3f3f;
11 typedef long long LL;
12 const int mod=1e9+7;
13 const double PI=acos(-1);
14 const int maxn=1e5+10;
15 using namespace std;
16 
17 struct node
18 {
19     int t;
20     int m;
21 }a[100010];
22 
23 LL ans;
24 priority_queue<int ,vector<int>,greater<int> >q;
25 bool cmp(node a,node b)
26 {
27     return a.t<b.t;
28 }
29 
30 int main()
31 {
32     int n;
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++)
35     {
36         scanf("%d %d",&a[i].t,&a[i].m);
37     }
38     sort(a+1,a+1+n,cmp);
39     for(int i=1;i<=n;i++)
40     {
41         if(a[i].t<=q.size())
42         {
43             if(a[i].m>q.top())
44             {
45                 ans-=q.top();
46                 q.pop();
47                 q.push(a[i].m);
48                 ans+=a[i].m;
49             }
50         }
51         else
52         {
53             q.push(a[i].m);
54             ans+=a[i].m;
55         }
56     }
57     printf("%lldn",ans);
58     return 0;
59 }