問題:
http://ace.delos.com/usacoprob2?a=sAaEFWx5xo1&S=milk2思路:
如果想通了，該題還是挺簡單的
首先按照開始時(shí)間進(jìn)行排序，然后依次查看相鄰時(shí)間段是否可以合并
針對合并后的時(shí)間段，很容易即可求出解
代碼:
1 /*
2 ID: simplyz2
3 LANG: C
4 TASK: milk2
5 */
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<string.h>
9 #define MAX_LEN 5001
10 #define Max(a,b) ((a)>(b) ? (a) : (b))
11 struct Intv {
12 int begin, end;
13 } intvs[MAX_LEN], merge[MAX_LEN];
14 int num, m_num;
15
16 int
17 compare(const void *arg1, const void *arg2)
18 {
19 return (((struct Intv *)arg1)->begin - ((struct Intv *)arg2)->begin);
20 }
21
22 void
23 merge_intv()
24 {
25 int i;
26 m_num = 0;
27 qsort(intvs, num, sizeof(struct Intv), compare);
28 merge[m_num] = intvs[0];
29 for(i=1; i<num; i++) {
30 if(intvs[i].begin > merge[m_num].end)
31 merge[++m_num] = intvs[i];
32 else if(intvs[i].end > merge[m_num].end)
33 merge[m_num].end = intvs[i].end;
34 }
35 }
36
37 void
38 solve()
39 {
40 int i, rt_a, rt_b;
41 rt_a = rt_b = 0;
42 for(i=0; i<=m_num; i++) {
43 rt_a = Max(rt_a, merge[i].end - merge[i].begin);
44 if(i)
45 rt_b = Max(rt_b, merge[i].begin - merge[i-1].end);
46 }
47 printf("%d %d\n", rt_a, rt_b);
48 }
49
50 int
51 main(int argc, char **argv)
52 {
53 int i;
54 freopen("milk2.in", "r", stdin);
55 freopen("milk2.out", "w", stdout);
56 while(scanf("%d", &num) != EOF) {
57 for(i=0; i<num; i++)
58 scanf("%d %d", &intvs[i].begin, &intvs[i].end);
59 merge_intv();
60 solve();
61 }
62 return 0;
63 }