usaco Milking Cows

题目链接：http://cerberus.delos.com:791/usacoprob2?a=bv3dg9ejwKm&S=milk2 这题目不是线段树，直接模拟

/*
ID: zypz4571
LANG: C++
TASK: milk2
*/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct Node {
    int s, t;
}a[5002];
bool cmp(const Node &a, const Node &b)
{
    return a.s < b.s;
}
int main(void)
{
    freopen("milk2.in", "r", stdin);
    freopen("milk2.out", "w", stdout);
    int n; scanf("%d",&n);
    for (int i = 0; i < n; scanf("%d%d",&a[i].s, &a[i].t),++i);
    sort(a,a+n,cmp);
    int Maxmilk=a[0].t-a[0].s, Maxidle=0, now = a[0].t, milk=Maxmilk, idle=0;
    for (int i = 1; i < n; ++i) {
        if (now >= a[i].t) continue;
        if (now >= a[i].s) {
            milk += (a[i].t - now), now = a[i].t, Maxmilk = max(Maxmilk, milk);
        }
        if (now < a[i].s) {
            idle = a[i].s - now, Maxidle = max(Maxidle, idle), milk = a[i].t - a[i].s,
            Maxmilk = max(milk, Maxmilk), now = a[i].t;
        }
    }
    printf("%d %d\n", Maxmilk, Maxidle);

    return 0;
}

=_=开始想太多……