[USACO][Section 1.2][贪心] Milking Cows

题目大意：

给出n个区间的上下界，求出最大连续区间的长度，几个连续区间之间的最大间隔。

思路：

把区间按照“上界由小到大，下界由大到小”的顺序排序并遍历，维护每个“连续区间”的上下界。判断一个区间是否与当前连续区间相连，只需要比较其下界与连续区间上界的大小关系即可。

若区间i不与当前连续区间相连，则新建一个连续区间（更新连续区间的上下界为区间i的上下界）。若区间i与当前连续区间相连，则（在区间i大于当前连续区间上界的情况下）更新连续区间的上界。

代码：

/*
ID: lujunda1
LANG: C++
PROG: milk2
*/
#include
#include
#include
#include
#include
using namespace std;
//定义结构体，用于将每个区间的”上下界“封装起来，便于对区间进行排序。 
struct point
{
    int low;
    int high;
}range[5000];
//排序规则是：优先按照下界由小到大排序，若下界相同，则按照上界由小到大顺序排序。 
int cmp(const void* m,const void* n)
{
    if((*(point*)m).low==(*(point*)n).low)
        return (*(point*)m).high-(*(point*)n).high;
    return (*(point*)m).low-(*(point*)n).low;
} 
int main()
{
    freopen("milk2.in","r",stdin);
    freopen("milk2.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=0;irange[i].high?temp_high:range[i].high;
        ///若区间i的下界大于当前连续区间的上界
        else
        {
            //更新最大间隔 
            idle=idle>range[i].low-temp_high?idle:range[i].low-temp_high;
            //更新当前连续区间的上下界 
            temp_high=range[i].high;
            temp_low=range[i].low;
        }
        //更新当前连续区间的长度 
        temp_max=temp_high-temp_low;
        //更新连续区间长度最大值 
        max=max>temp_max?max:temp_max;
    }
    printf("%d %d\n",max,idle);
}