【区间覆盖】USACO Milking Cows

KIDx的解题报告

 

进入USACO要注册才能看题: http://train.usaco.org/usacogate

题目：【翻译版、是别处的网站】http://www.wzoi.org/usaco/12%5C211.asp

SAMPLE INPUT (file milk2.in)
3
300 1000
700 1200
1500 2100
SAMPLE OUTPUT (file milk2.out)
900 300

/*
ID: 1006100071
LANG: C++
TASK: milk2
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define M 5005

struct times{
	int a, b;    //a区间开端，b区间末端
}x[M];

int end[M];

bool cmp (times x, times y)
{
	if (x.a == y.a)
		return x.b < y.b;
	return x.a < y.a;
}

int main()
{
	/*freopen ("milk2.in", "r", stdin);
	freopen ("milk2.out", "w", stdout);*/
	int n, i, start, maxs, maxs2;
	scanf ("%d", &n);
	for (i = 0; i < n; i++)
		scanf ("%d%d", &x[i].a, &x[i].b);
	sort (x, x+n, cmp);
	//end[i]--------------------储存前i个【包括i】区间的最大末端
	end[0] = x[0].b;
	for (i = 1; i < n; i++)
	{
		if (x[i].b > end[i-1])
			end[i] = x[i].b;
		else end[i] = end[i-1];
	}
	//求最大连续覆盖长度
	start = maxs = 0;
	for (i = 0; i < n; i++)
	{
		if (i+1 < n && x[i+1].a <= end[i])
			continue;
		else
		{
			int tp = end[i] - x[start].a;
			if (tp > maxs) maxs = tp;
			start = i + 1;
		}
	}
	//求最大区间间隔【间隔是空白区域】 
	maxs2 = 0;
	for (i = 1; i < n; i++)
		if (x[i].a > end[i-1] && maxs2 < x[i].a - end[i-1])
			maxs2 = x[i].a - end[i-1];
	printf ("%d %d\n", maxs, maxs2);
	return 0;
}