BZOJ 1572: [Usaco2009 Open]工作安排Job

题目地址

描述

Farmer John 有太多的工作要做啊!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。
他的工作日从$0$时刻开始,有$1000000000$个单位时间。在任一时刻,他都可以选择编号$1 \sim N$的$N(1 \leq N \leq 100000)$项工作中的任意一项工作来完成。
因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有$N$个工作,虽然还是有可能。 对于第i个工作,有一个截止时间$D_{i}(1 \leq D_{i} \leq 1000000000)$,如果他可以完成这个工作,那么他可以获利$P_{i}( 1 \leq P_{i} \leq 1000000000 )$。在给定的工作利润和截止时间下,FJ能够获得的利润最大为多少呢?答案可能会超过32位整型。

分析

很典型的贪心题。

首先还是按照时间顺序排序,若时间相同按照利润的大小从小到大排序。

首先先加上所有的工作的利润,然后用按照从小到大排序的优先队列筛去同一时间但是利润不是最大的那个工作,最后就可以得到答案。

最近又开始划水了,sigh

代码

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
//2017/6/11 23:43
//Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
//BZOJ 1572 [Usaco2009 Open]工作安排Job
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readIn(){
ll x = 0;
int f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return (ll)x * f;
}
const int MAX = 100000 + 3;
int n;
struct Work{
ll dl, p;//deadline, profits;
bool operator < (const Work &rhs) const{
if(dl == rhs.dl) return p < rhs.p;dl < rhs.dl;
return dl < rhs.dl;
}
}work[MAX];
priority_queue< ll, vector<ll>, greater<ll> > q;//按照从小到大的顺序排序

int main()
{
n = readIn();
for(int i = 0; i < n; ++i) {
work[i].dl = readIn(), work[i].p = readIn();
}
sort(work, work + n);

ll ans = 0, sum = 0;
for(int i = 0; i < n; ++i){
ans += work[i].p;
sum++;
q.push(work[i].p);
if(sum > work[i].dl){
ans -= q.top(); q.pop();
sum--;
}
}
printf("%lld\n", ans);
return 0;
}
Partager