AcWing 畜栏预定

骑猪看日落 2021-11-10 02:32 213阅读 0赞

## AcWing 畜栏预定 ##

### Description ###

*  有N头牛在畜栏中吃草。
    
    每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
    
    给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在\[A,B\]这一时间段内都会一直吃草。
    
    当两头牛的吃草区间存在交集时（**包括端点**），这两头牛不能被安排在同一个畜栏吃草。
    
    求需要的最小畜栏数目和每头牛对应的畜栏方案。

### Input ###

*  第1行：输入一个整数N。
    
    第2..N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。

### Output ###

*  第1行：输入一个整数，代表所需最小畜栏数。
    
    第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号从1开始，只要方案合法即可。

### Data Size ###

*  1≤N≤50000,  
    1≤A,B≤1000000

### Sample Input ###

>     5
>     1 10
>     2 4
>     3 6
>     5 8
>     4 7

### Sample Output ###

>     4
>     1
>     2
>     3
>     2
>     4

### 题解： ###

*  贪心。
 *  贪心思路按照正常人思路。就是先按开始时间排序。然后依次加入奶牛，如果发现有一头奶牛消费完了，就赶紧把它拿出来让当前奶牛进去。如果没有发现任意一头奶牛消费完了，那么只能给当前奶牛再开一个房间了。
 *  “发现有一头奶牛消费完了”这个操作，也就是找消费的奶牛里结束时间最早的那一头。可以用堆来维护

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #define N 50005 using namespace std; struct Node { int l, r, id; friend bool operator < (Node x, Node y) { return x.r > y.r; } }; priority_queue<Node> que; struct A {int l, r, id, ans;} a[N]; int n, cnt; bool cmp1(A x, A y) {return x.l < y.l;} bool cmp2(A x, A y) {return x.id < y.id;} int read() { int x = 0; char c = getchar(); while(c < '0' ||c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x; } int main() { cin >> n; for(int i = 1; i <= n; i++) a[i].l = read(), a[i].r = read(), a[i].id = i; sort(a + 1, a + 1 + n, cmp1); que.push((Node){a[1].l, a[1].r, ++cnt}); a[1].ans = cnt; for(int i = 2; i <= n; i++) { if(que.top().r < a[i].l) { a[i].ans = que.top().id; que.pop(); que.push((Node){a[i].l, a[i].r, a[i].ans}); } else { a[i].ans = ++cnt; que.push((Node){a[i].l, a[i].r, cnt}); } } cout << cnt << endl; sort(a + 1, a + 1 + n, cmp2); for(int i = 1; i <= n; i++) printf("%d\n", a[i].ans); return 0; }

转载于:https://www.cnblogs.com/BigYellowDog/p/11281603.html