[AtCoder] ABC 160 C – Traveling Salesman around Lake

2020年3月31日2020年12月15日

問題

方針

\( e_i \) を家 \( i \) と \( i + 1 \) との距離とすると、\( e_i = A_{i + 1} – A_i \) となります。ただし、\( e_N = K – A_N + A_1 \) とします。最短移動をするとき、\( e_i \) のどれかの移動は行わないので、\( e_i \) の最大値を \( v \) とすると、\( K – v \) が答えになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll K;
    int N;
    cin >> K >> N;
    ll A[N];
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll e[N];
    for (int i = 0; i < N - 1; i++) {
        e[i] = A[i + 1] - A[i];
    }
    e[N - 1] = K - A[N - 1] + A[0];
    ll v = e[0];
    for (ll i : e) {
        v = max(i, v);
    }
    cout << K - v << "\n";
    return 0;
}