luogu P2859 [USACO06FEB]摊位预订

YorkWu

September 12, 2019

1303 views

No comments

586 words

OI 题目

一道蓝题贪心

- 对于输入的时间，先按照起始时间排个序。
- 先把第一个奶牛的结束时间插入到优先队列（小根堆）中，对于第2到n的奶牛：
    1. 取出堆顶，其结束时间若小于当前奶牛开始时间，便让当前奶牛使用的牛棚设置为堆顶那个奶牛使用的牛棚
    2. 若其结束时间大于当前奶牛开始时间，由于已经按照起始时间排序，所以当前奶牛不能用现有牛棚，之后的奶牛也肯定不能，所以新建一个牛棚，让这个奶牛使用。

```cpp
#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;
}
```

Last modification：March 14, 2020