luogu P2859 [USACO06FEB]摊位预订

一道蓝题贪心

  • 对于输入的时间,先按照起始时间排个序。
  • 先把第一个奶牛的结束时间插入到优先队列(小根堆)中,对于第2到n的奶牛:
    1. 取出堆顶,其结束时间若小于当前奶牛开始时间,便让当前奶牛使用的牛棚设置为堆顶那个奶牛使用的牛棚
    2. 若其结束时间大于当前奶牛开始时间,由于已经按照起始时间排序,所以当前奶牛不能用现有牛棚,之后的奶牛也肯定不能,所以新建一个牛棚,让这个奶牛使用。
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
#include<bits/stdc++.h>
using namespace std;

struct node{
int a, b, id, use;
};

bool cmp1(const node &a, const node &b){
return a.a < b.a;
}

bool cmp2(const node &a, const node &b){
return a.id < b.id;
}

struct Solution{
int n;
vector<node> a;

void Solve(){
scanf("%d", &n);
a.resize(n + 1);
for(int i = 1; i <= n; i++){
scanf("%d%d", &a[i].a, &a[i].b);
a[i].id = i;
}
sort(a.begin() + 1, a.end(), cmp1);
priority_queue<pair<int, int> > pq;
int num = 1;
pq.push(make_pair(-a[1].b, num));
a[1].use = 1;
for(int i = 2; i <= n; i++){
int last = -pq.top().first;
int lnum = pq.top().second;
if(last < a[i].a){
pq.pop();
a[i].use = lnum;
pq.push(make_pair(-a[i].b, lnum));
}
else{
num++;
a[i].use = num;
pq.push(make_pair(-a[i].b, num));
}
}
sort(a.begin() + 1, a.end(), cmp2);
printf("%d\n", num);
for(int i = 1; i <= n; i++){
printf("%d\n", a[i].use);
}
}
};

int main(){
Solution().Solve();
return 0;
}
# 贪心

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×