POJ 3190 Stall Reservations 《挑战程序设计竞赛(第2版)》练习题答案

2.2 一往直前！贪心法 区间

POJ 3190 Stall Reservations

还是该死的奶牛，这一回它们很淘气，每一只奶牛要求在时间区间[A,B]内独享一个牛栏。问最少需要多少个牛栏。

贪心策略是优先满足A最小的奶牛，维持一个牛栏B最小堆，将新来的奶牛塞进B最小的牛栏里。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Section
{
	unsigned int index;
	unsigned int begin;
	unsigned int end;
	bool operator < (const Section& b) const 
	{  
		return begin < b.begin;
	} 
};

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

#define MAX_COWS 50000
Section cow[MAX_COWS];
unsigned int result[MAX_COWS]; // 每头牛从属于哪个牛栏
priority_queue<Stall> que; // 最小堆，储存所有牛栏区间的结束点（也就是最右端）

inline void put_cow(const int& i, const bool& new_stall)
{
	Stall s;
	if (new_stall)
	{
		s.id = que.size() + 1;
	}
	else
	{
		s.id = que.top().id; que.pop();
	}
	s.end = cow[i].end;
	result[cow[i].index] = s.id;
	que.push(s);
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cow[i].index = i;
		cin >> cow[i].begin;
		cin >> cow[i].end;
	}

	sort(cow, cow + N);
	put_cow(0, true);

	for (int i = 1; i < N; ++i)
	{
		put_cow (i, cow[i].begin <= que.top().end);
	}

	cout << que.size() << endl;
	for (int i = 0; i < N; ++i)
	{
		cout << result[i] << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3190 Stall Reservations 《挑战程序设计竞赛(第2版)》练习题答案