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;
}
分享到:
相关推荐
USACO题目Milking Cows及代码解析
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
6 [1.2] 挤牛奶Milking Cows 7 [1.2] 方块转换 Transformations 8 [1.2] 回文平方数 Palindromic Squares 9 [1.2] 双重回文数 Dual Palindromes 10 [1.3] 混合牛奶 Mixing Milk 11 [1.3] 修理牛棚 Barn Repair 12 ...
P8898 [USACO22DEC] Feeding the Cows B 题解.docx
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO题集及答案
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO历年比赛测试数据:2003年 方便大家测试
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
内含USACO全部测试数据,绝对全
USACO全部译题 USACO Training Program Gateway
usaco traning的全部数据 才要3分
自己前一段时间在坐usaco上的题目,一遍看题解,一遍做,做到第三章,就做不动了,发一些源程序和测试数据。
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
USACO所有题目的题解 NOCOW整理版
USACO历年比赛测试数据:2006年方便大家测试
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!