POJ 1304 - World's Worst Bus Schedule

http://poj.org/problem?id=1304

概要

\(N\) 個のバスがあり、\(i\) 番目のバスは \(r_{i, 1}\) で一周、 \(r_{i, 2}\) で一周、 …、 \(r_{i, M}\) で一周、 そして \(r_{i, 1}\) で一周、と周回している。

バス停についた時刻が \(t\) のとき、次にバスがくる時刻を答える。 どのバスも時刻 0 でこのバス停を出発して周回を始めたとする。

制約

解法

各バスについて、1周期で割った余りから次に何時にくるか調べるだけ。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <numeric>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   for (string s; getline(cin, s) && s != "ENDOFINPUT";) {
10     int N;
11     {
12       istringstream iss(s);
13       iss >> s >> N;
14     }
15     vector<vector<int> > v(N);
16     for (int i = 0; i < N; i++) {
17       getline(cin, s);
18       istringstream iss(s);
19       for (int x; iss >> x;) {
20         v[i].push_back(x);
21       }
22     }
23     int T;
24     {
25       getline(cin, s);
26       istringstream iss(s);
27       iss >> T;
28     }
29     getline(cin, s);
30 
31     int ans = 10000000;
32     for (int i = 0; i < N; i++) {
33       int t = T % accumulate(v[i].begin(), v[i].end(), 0);
34       if (t == 0) {
35         ans = 0;
36         break;
37       }
38       int acc = 0;
39       for (vector<int>::const_iterator it = v[i].begin(); it != v[i].end(); ++it) {
40         acc += *it;
41         if (acc >= t) {
42           ans = min(ans, acc-t);
43           break;
44         }
45       }
46     }
47     cout << ans << endl;
48   }
49   return 0;
50 }
poj/1304.cc