放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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版)》练习题答案

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    bool operator < (const Stall& b) const
    {
    return end > b.end;
    }
    这里不是小于号吗,为什么重载的内容是大于号

    奥特曼3年前 (2015-02-27)回复
    • <表示从小到大,>表示希望逆序排序

      hankcs3年前 (2015-02-27)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机