superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 1.2 - Milking Cows

Posted on 2009-03-12 15:17 superman 阅读(123) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理