aoj0299:Railroad Ⅱ

問題文

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

解法

まず、pが0番目の駅になるようにm個の目的地の番号を変化させます。
すると、少し扱いやすくなります。

(僕の解法では)m==1の場合は特別なので、そこだけ場合分けします。

それ以外は、次のように解きました。

まず、目的地を番号が昇順になるようにソートします。

答えとなる経路の候補はそこそこ少ない(mの定数倍個くらい)ので、それを全部試します。

具体的には、次の4種類の経路があるので、それらの経路の移動コストの最小値を取ります。
それぞれの経路の移動コストはO(1)で求まります。

1:最も番号が小さい目的地に半時計周りに行く経路

2:最も番号が大きい目的地に時計周りに行く経路

3:i番目()に時計周りに行ったあと一旦来た道を戻って、そしてi+1番目の目的地に半時計周りに行く経路

4:i+1番目()に半時計周りに行った後一旦来た道を戻って、そしてi番目の目的地に時計周りに行く経路

ソートに一番時間がかかると思われるので、O(mlogm)くらいです。

コード

#include<bits/stdc++.h>
using namespace std;
 
int n,m,p;
int d[10000];
int main(){
    cin>>n>>m>>p;p--;
    for(int i=0;i<m;i++){
        cin>>d[i];
        d[i]--;
 
        d[i]=(d[i]-p+n)%n;
    }
 
    if(m==1){
        cout<<min(d[0],n-d[0])*100<<endl;
        return 0;
    }
 
    sort(d,d+m);
 
    int mi=min(n-d[0],d[m-1]);
    for(int i=0;i<m-1;i++){
        mi=min(mi,d[i]*2+n-d[i+1]);
        mi=min(mi,(n-d[i+1])*2+d[i]);
    }
 
    cout<<mi*100<<endl;
    return 0;
}