AOJ 0299 Railroad II

競プロ AOJ

問題

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

解法

d(i) をソートし，かつ p が 0 となるようにずらしておく．
ちょっと考えると，解の候補としては

  • d(1) まで反時計回りで一周する
  • d(M) まで時計回りで一周する
  • d(i) まで時計回りで訪れた後，そこから反時計回りで d(i+1) まで訪れる
  • d(i+1) まで反時計回りで訪れた後，そこから時計回りで d(i) まで訪れる

の4通りしかないことが分かる．
あとはこれを実装するだけ．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, M, p;
    cin >> N >> M >> p;
    vector<int> d(M);
    for(int i=0; i<M; ++i) {
        cin >> d[i];
        d[i] -= p;
        d[i] = (d[i] + N) % N;
    }
    sort(d.begin(), d.end());
    int res = min(d.back(), N - d[0]);
    for(int i=0; i<M-1; ++i) {
        res = min(res, min(2*d[i] + (N - d[i+1]), 2*(N - d[i+1]) + d[i]));
    }
    cout << res * 100 << endl;
}