贪心_POJ3190_Stall Reservations

点此打开题目页面

思路分析:

    考虑这样的贪心策略, 将所有奶牛按照开始挤奶时间非递减排序并引入一个以当前每个挤奶槽位上最后一头牛挤奶结束时间为关键字的最小堆, 对于每头牛, 如果最小堆堆顶的关键字小于该牛挤奶开始时间, 那么从堆中取出该槽位, 并将该槽位分配给这头牛, 更新该槽位的结束时间后重新加入堆中, 重复此过程, 直至所有奶牛均已考察, 可以证明该贪心策略正确, 下面给出AC代码:

//POJ3190_Stall Reservations 
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;
const int MAXN = 5e4 + 5;
pair<pair<int, int>, int> cow[MAXN];//first.first:开始挤奶时间, first.second:结束挤奶时间,second:牛编号,后用来记录方案,first:牛编号,second:槽编号 
priority_queue<pair<int, int>, deque<pair<int, int> >, greater<pair<int, int> > > h;//first:最后一头牛占用时间, second:槽编号 
int main(){
	int N; scanf("%d", &N);
	for(int i = 1; i <= N; ++i) 
		scanf("%d %d", &cow[i].first.first, &cow[i].first.second), cow[i].second = i; 
	sort(cow + 1, cow + N + 1);
	for(int i = 1, t; i <= N; ++i)
		if(h.empty() || h.top().first >= cow[i].first.first) 
			h.push(make_pair(cow[i].first.second, h.size() + 1))
			, cow[i].first.first = cow[i].second, cow[i].first.second = h.size();
		else
			t = h.top().second, h.pop(), h.push(make_pair(cow[i].first.second, t))
			, cow[i].first.first = cow[i].second, cow[i].first.second = t;
	cout << h.size() << endl; 
	sort(cow + 1, cow + N + 1); for(int i = 1; i <= N; ++i) cout << cow[i].first.second << endl;
	return 0;
}