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; }
?