题目地址:http://poj.org/problem?id=3190

题目大意

有N头牛,在一些畜栏中吃草,每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏,给定N头牛和每头牛开始吃草和结束吃草的时间,求使用最小畜栏数目和每头牛对应的畜栏。

思路

用最小堆来维护牛栏结束的时间,当牛的结束时间小于牛栏最早结束时间时,则再开一间牛栏,否则将该牛放进去,并更新牛栏结束时间。

AC代码

/*************************************************************************
    > File Name: 3190.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-09-08 二 20:25:03 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

// 有N头牛,在一些畜栏中吃草,每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏,给定  N 头牛和每头牛开始吃草和结束吃草的时间,求使用最小畜栏数目和每头牛对应的畜栏。
struct Cow {
    int start, end, id;
    bool operator<(const Cow &b) const {
        return start < b.start;
    }
} cow[50005];

struct Stall {
    int id, end;
    bool operator <(const Stall &b) const {
        return end > b.end;
    }
    Stall() {}
    Stall(int id, int end) : id(id), end(end) {}
};

int N;
int res[50005];

void solve() {
    sort(cow, cow+N);
    // for(int i=0; i<N; ++i)
        // printf("%d %d\n", cow[i].start, cow[i].end);
    priority_queue<Stall> que;
    que.push(Stall(1, cow[0].end));
    Stall s;
    res[cow[0].id] = 1;
    for(int i=1; i<N; ++i) {
        if(cow[i].start <=que.top().end)
            s.id = que.size()+1; // 在开一间牛栏
        else {
            s.id = que.top().id; que.pop(); // 放进已有牛栏
        }
        s.end = cow[i].end;
        res[cow[i].id] = s.id;
        que.push(s);
    }
    cout << que.size() << endl;
    for(int i=0; i<N; ++i)
        cout << res[i] << endl;
}

int main()
{
#ifdef Oj
    freopen("3190.in", "r", stdin);
#endif
    scanf("%d", &N);
    for(int i=0; i<N; ++i) {
        scanf("%d%d", &cow[i].start, &cow[i].end);
        cow[i].id = i;
    }
    solve();

    return 0;
}