C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1163 最高的奖励

Problem

有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。

Solution

时间排序,小根堆,每次加入,如果数量小于时间就加入,否则弹出一个加入。

Code

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<string.h>
#include<stack>

#define mem(ss) memset(ss,0,sizeof(ss))
#define fo(d, s, t) for(int d=s;d<=t;d++)
#define fo0(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 998244353;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

db fab(db x) {
return x > 0 ? x : -x;
}

int n;

struct E {
int t, w;

bool operator<(const E &x) const {
return this->w > x.w;
}
} e[50020];

int cmp(E x, E y) {
return x.t < y.t;
}
priority_queue<E>q;
int cnt;
ll ans;
int main() {
scanf("%d", &n);
fo(i, 1, n) {
scanf("%d%d", &e[i].t, &e[i].w);
}
sort(e + 1, e + 1 + n, cmp);
fo(i,1,n){
if(cnt<e[i].t){
q.push(e[i]);
cnt++;
}
else{
if(e[i].w>q.top().w){
q.pop();
q.push(e[i]);
}
}
}
while(!q.empty()){
ans+=q.top().w;
q.pop();
}
printf("%lld\n",ans);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/45564/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!