//译题 ★Milking Cows 挤牛奶 三个农民每天清晨5 点起床,然后去牛棚给3 头牛挤奶.第一个农民在300 时刻(从5 点开始计时, 秒为单位)给他的牛挤奶,一直到1000 时刻.第二个农民在700 时刻开始,在 1200 时刻结束.第三个 农民在1500 时刻开始2100 时刻结束.期间最长的至少有一个农民在挤奶的连续时间为900 秒(从 300 时刻到1200 时刻),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300 秒(从 1200 时刻到1500 时刻). 你的任务是编一个程序,读入一个有N 个农民(1 <= N <= 5000)挤N 头牛的工作时间列表,计算以下 两点(均以秒为单位): • 最长至少有一人在挤奶的时间段. • 最长的无人挤奶的时间段. PROGRAM NAME: milk2 INPUT FORMAT Line 1: 一个整数N. Lines 2..N+1: 每行两个小于1000000 的非负整数,表示一个农民的开始时刻与结束时刻. SAMPLE INPUT (file milk2.in) 3 300 1000 700 1200 1500 2100 OUTPUT FORMAT 一行,两个整数,即题目所要求的两个答案. SAMPLE OUTPUT (file milk2.out) 900 300
/* ID: china_l5 LANG: C TASK: milk2 */ #include<stdio.h> #include<math.h> #define MAXN 5000 + 10 /* 按照开始时间升序排序，然后从左到右扫一遍，复杂度是O(nlogn+n)的（排序+扫一遍，用堆、合并、快排都可以）。 所谓从左到右扫一遍，就是记录一个当前区间，[tmp_begin,tmp_end]。 如果下一组数据的begin比tmp_end的小（或相等），则是连接起来的，检查这组数据的end，取max{end,tmp_end}。 如果下一组数据的begin比tmp_end的大，则是相互断开的，整理本区间，ans1取max{tmp_end - tmp_begin,ans1}。ans2取max{begin - tmp_end,ans2}。 看不懂？去看看PASCAL或C的范例程序就明白了。 线段 */ void swap(int *a, int *b) //用于排序 { int t = *a; *a = *b; *b = t; } int main() { int a[2][MAXN]={0}; //存放n个农民工作的时间区间 int i, j, tmp, n; int max1=0, max2=0; //max1存放最长至少有一人在挤奶的时间段.， max2存放最长的无人挤奶的时间段. int cur[2]={0}; //用于存区间，cur[0]存起始时间 cur[1]存结束时间 freopen("milk2.in", "r", stdin); freopen("milk2.out", "w", stdout); scanf("%d", &n); //读入n for(i=0;i<n;i++) //读入时间 scanf("%d %d",&a[0][i],&a[1][i]); for(i=0;i<n-1;i++) //将时间按照起始时间从小到大排序， for(j=0;j<n-1-i;j++) { if(a[0][j+1] < a[0][j]) { swap(&a[0][j+1],&a[0][j]); swap(&a[1][j+1],&a[1][j]); } } cur[0]=a[0][0]; //默认起始时间为a｛0][0]； cur[1]=a[1][0]; for(i=1;i<n;i++) //这里是这题的关键，前面不管你用什么方法，就是排个序就行了 { if(a[0][i] > cur[1]) //如果本组数据的begin比上一组数据的end的大，说明是有间断存在的 { tmp = a[0][i] - cur[1]; //tmp==无人挤奶的时间 if(tmp > max2) //tmp 与 max2进行比较 max2 = tmp; tmp = cur[1] - cur [0]; //tmp == 上一组数据的时间段 if(tmp > max1) max1 = tmp; cur[0] = a[0][i]; //cur的值改变为本组数据的值 cur[1] = a[1][i]; } else { if(a[1][i] > cur[1]) //如果本组数据的end > 上一组数据的end cur[1] = a[1][i]; } } tmp = cur[1] - cur[0]; //求出最大的有人工作的时间 if(tmp > max1) max1 = tmp; printf("%d %d ", max1, max2); return 0; }