POJ 3618 - Exploration

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

概要

数直線上に N 個のランドマークがあり，それぞれ座標 x[1], ..., x[N] に位置している．

原点からスタートし，原点からの距離が近いランドマークから順に巡っていくとき，T 分以内にいくつのランドマークへ行けるかを答える．

1分で単位距離進めるものとする．

制約

解法

言われた通りにシミュレーションして数える．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N;
 9   long long T;
10   scanf("%lld %d", &T, &N);
11   vector<int> left, right;
12   for (int i = 0; i < N; i++) {
13     int x;
14     scanf("%d", &x);
15     if (x >= 0) {
16       right.push_back(x);
17     } else {
18       left.push_back(-x);
19     }
20   }
21   sort(right.begin(), right.end());
22   sort(left.begin(), left.end());
23 
24   vector<int>::const_iterator it = right.begin(), jt = left.begin();
25   int ans = 0;
26   int pos = 0;
27   for (int i = 0; i < N && T > 0LL; i++) {
28     if (it == right.end()) {
29       T -= abs(pos + *jt);
30       pos = -*jt;
31       ++jt;
32     } else if (jt == left.end()) {
33       T -= abs(pos - *it);
34       pos = *it;
35       ++it;
36     } else if (*it < *jt) {
37       T -= abs(pos - *it);
38       pos = *it;
39       ++it;
40     } else {
41       T -= abs(pos + *jt);
42       pos = -*jt;
43       ++jt;
44     }
45     if (T >= 0LL) {
46       ++ans;
47     }
48   }
49   printf("%d\n", ans);
50   return 0;
51 }
poj/3618.cc