【USACO题库】1.2.1 Milking Cows挤牛奶

题目描述 三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300时刻(从5点开始计时，秒为单位)给他的牛挤奶，一直到1000时刻。第二个农民在700时刻开始，在 1200时刻结束。第三个农民在1500时刻开始2100时刻结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200时刻到1500时刻 你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位): 最长至少有一人在挤奶的时间段。 最长的无人挤奶的时间段。 输入 Line 1: 一个整数N。 Lines 2..N+1: 每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。 输出 一行，两个整数，即题目所要求的两个答案。 样例输入 3 300 1000 700 1200 1500 2100 样例输出

900 300

这题坑啊。。。

这道题我们先以开始时刻为第一关键字从小到大，以结束时刻为第二关键字从大到小快排。

之后定两个变量b1和e1，表示经过排序后第一个时间段的开始时间和结束时间，再定max1和max2，表示最长有人的时间段和最长无人的时间段，把max1设定为第一个时间段（即e1-b1）

之后我们依次枚举剩下的时间段。

例如这是样例：

刚开始b1为300，e1为1000。

之后我们与下一个时间段比较，发现它们可以合为一个时间段。

于是e1变成了1200。

再和第三条时间段比较，发现它们中间有时间空隙，不能合为一条时间段。

于是我们就先计算一下当前的时间长度是否比两个max大。

max1初始为300，而现在的时间段长度为（1200-300）=900，所以max1变为900；

而max2初始为0，现在的时间段长度为（1500-1200）=300，所以max2变为300。

然后把b1和e1变为第三条时间段的开始时间和结束时间（即1500和2100）。

最后再计算一下最后一段的长度，

max1为900，而（2100-1500）=600，所以我们不用更新。

最后max1为900，而max2为300，就是样例的答案。

其它的数据也是这样算。