POJ 2376 Cleaning Shifts 《挑战程序设计竞赛(第2版)》练习题答案

2.2 一往直前！贪心法 区间

POJ 2376 Cleaning Shifts

给定N个小区间以及区间起点终点，求能用它们覆盖区间[1,T]的最小组合。

贪心策略是从左往右，尽量选择长度最大的区间。

首先对所有奶牛排序，按照开始时间排序。

然后更新起点=终点+1，搜索剩下的奶牛中能够覆盖这个起点同时终点最远的那一头，更新终点。

#include <iostream>
#include <algorithm>
using namespace std;
int N, T;

struct Cow
{
	int begin;	// 开始时间 
	int end;	// 结束时间 
};

#define MAX_COWS 25000
Cow cow[MAX_COWS];

bool is_greater(const Cow& a, const Cow& b)
{
	return a.begin < b.begin || (a.begin == b.begin && a.end > b.end);
}

int solve()
{
	int used_cows = 0;
	int end = 0;
	int index = 0;
	while(end < T)
	{
		int begin = end + 1;
		// 寻找一头既能从begin干起，又能一直干到最远的牛 
		for (int i = index; i < N; ++i)
		{
			if (cow[i].begin <= begin)
			{
				// 能够覆盖起始点 
				if (cow[i].end >= begin)
				{
					// 将终点延长到最远 
					end = max(end, cow[i].end);
				}
			}
			else
			{
				// 不能覆盖起始点，说明上一头牛的终点就是最远点，需要换一头牛了 
				index = i;
				break;
			}
		}

		// 没找到这样的牛，这个case失败 
		if (begin > end)
		{
			return -1;
		}
		else
		{
			++used_cows;
		}
	}

	return used_cows;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	cin >> N >> T;
	for (int i = 0; i < N; ++i)
	{
		cin >> cow[i].begin >> cow[i].end;
	}
	sort(cow, cow + N, is_greater);
	cout << solve() << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

发生了一个小插曲，提交POJ的时候报编译错误：

• Compile Error

Main.cpp
F:\temp\12494919.90217\Main.cpp(76) : fatal error C1071: unexpected end of file found in comment

原因是我使用了中文注释或中文空格，删除所有中文注释提交AC。又试了一次，保留所有中文注释，在最后一行回车然后提交，AC。

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