POJ 3505 - Tower Parking

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

概要

各階に円形のベルトコンベアがあり，l 台の車を載せることができる． それらのベルトコンベアをエレベーターが繋いでおり，1階から h 階まである．

ベルトコンベアは時計回りまたは反時計回りに回すことができ，1台分動かすのに5秒かかる． 一方エレベーターは1階分移動するのに10秒かかる．

i 階の j 番目の位置に何番目に出すべき車があるかという情報が与えられるので，それに従って移動させたときにかかる最短の時間を答える．

制約

解法

シミュレーションするだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int T;
10   cin >> T;
11   while (T-- > 0) {
12     int H, L;
13     cin >> H >> L;
14     map<int, pair<int,int> > cars;
15     for (int i = 0; i < H; i++) {
16       for (int j = 0; j < L; j++) {
17         int r;
18         cin >> r;
19         if (r != -1) {
20           cars.insert(make_pair(r, make_pair(i, j)));
21         }
22       }
23     }
24 
25     vector<int> offset(H, 0);
26     int ans = 0;
27     for (map<int, pair<int,int> >::const_iterator it = cars.begin(); it != cars.end(); ++it) {
28       const int h = it->second.first;
29       const int l = it->second.second;
30       ans += 10*h;
31       const int x = abs(l - offset[h]);
32       ans += 5*min(x, L - x);
33       offset[h] = l;
34       ans += 10*h;
35     }
36     cout << ans << endl;
37   }
38   return 0;
39 }
poj/3505.cc