Posted on 2009-03-12 15:17
superman 阅读(124)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 struct Interval
6 {
7 int s, t;
8
9 bool operator < (const Interval & i) const
10 {
11 return s < i.s;
12 }
13 } interval[5000];
14
15 int main()
16 {
17 freopen("milk2.in", "r", stdin);
18 freopen("milk2.out", "w", stdout);
19
20 int n;
21
22 cin >> n;
23 for (int i = 0; i < n; i++)
24 cin >> interval[i].s >> interval[i].t;
25
26 sort(interval, interval + n);
27
28 int p = 0;
29
30 bool toBeDeleted[5000] = { false };
31 for (int i = 0; i < n - 1; i++)
32 for (int j = i + 1; interval[i].t > interval[j].t && j < n; j++)
33 toBeDeleted[j] = true;
34 for (int i = 0; i < n; i++)
35 if (toBeDeleted[i] == false)
36 {
37 interval[p].s = interval[i].s;
38 interval[p].t = interval[i].t;
39 p++;
40 }
41
42 n = p;
43
44 bool toBeUnited[5000] = { false };
45 for (int i = 1; i < n; i++)
46 if (interval[i].s <= interval[i - 1].t)
47 toBeUnited[i] = true;
48
49 p = 0;
50 for (int i = 0; i < n; )
51 {
52 int j = i;
53 while (toBeUnited[j + 1] == true)
54 j++;
55 if (i == j)
56 {
57 interval[p].s = interval[i].s;
58 interval[p].t = interval[i].t;
59 p++;
60 }
61 else
62 {
63 interval[p].s = interval[i].s;
64 interval[p].t = interval[j].t;
65 p++;
66 }
67 i = j + 1;
68 }
69
70 int longestContinuousTime = 0, longestIdleTime = 0;
71 for (int i = 0; i < p; i++)
72 longestContinuousTime >?= interval[i].t - interval[i].s;
73 for (int i = 0; i < p - 1; i++)
74 longestIdleTime >?= interval[i + 1].s - interval[i].t;
75
76 cout << longestContinuousTime << ' ' << longestIdleTime << endl;
77
78 return 0;
79 }
80