AOJ 1315 - Gift from the Goddess of Programming

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1315

概要

女神とプログラマたちの祭壇への出入りの記録が与えられるので，プログラマが女神と一緒にいた時間の最大値を答える．

ただし祭壇は 00:00 に閉められるため，入力の時間は 00:01 から 23:59 であり，女神やプログラマが 00:00 になっても出ていかないような入力は無い．

制約

• 入力行 <= 1000

解法

日付で区切り，その間の記録を見て女神と一緒にいた時間を足していくだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 using namespace std;
 5 
 6 int parse(const string& t)
 7 {
 8   return ((t[0]-'0')*10 + t[1]-'0')*60 + ((t[3]-'0')*10 + t[4]-'0');
 9 }
10 
11 int inter(int gb, int ge, int vb, int ve)
12 {
13   if (ge < vb || ve < gb) {
14     return 0;
15   } else {
16     return min(ge, ve) - max(gb, vb);
17   }
18 }
19 
20 void countup(map<string, int>& total, const map<string, vector<int> >& m)
21 {
22   if (!m.count("000")) {
23     return;
24   }
25   const vector<int>& god = m.find("000")->second;
26   const int N = god.size();
27   if (N % 2 != 0) {
28     throw "N is not even";
29   }
30   for (map<string, vector<int> >::const_iterator it = m.begin(); it != m.end(); ++it) {
31     if (it->first == "000") {
32       continue;
33     }
34     const string& id = it->first;
35     const vector<int>& v = it->second;
36     const int M = v.size();
37     if (M % 2 != 0) {
38       throw "M is not even";
39     }
40     for (int i = 0; i < N; i += 2) {
41       for (int j = 0; j < M; j += 2) {
42         total[id] += inter(god[i], god[i+1], v[j], v[j+1]);
43       }
44     }
45   }
46 }
47 
48 int main()
49 {
50   int N;
51   while (cin >> N && N != 0) {
52     string prev_date = "";
53     map<string, vector<int> > m;
54     map<string, int> total;
55     for (int i = 0; i < N; i++) {
56       string date, time, act, id;
57       cin >> date >> time >> act >> id;
58       if (date != prev_date) {
59         countup(total, m);
60         m.clear();
61       }
62       m[id].push_back(parse(time));
63       prev_date = date;
64     }
65     countup(total, m);
66     int ans = 0;
67     for (map<string, int>::const_iterator it = total.begin(); it != total.end(); ++it) {
68       ans = max(ans, it->second);
69     }
70     cout << ans << endl;
71   }
72   return 0;
73 }