放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

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

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》