Candles [AtCoder Regular Contest 101 C]

https://beta.atcoder.jp/contests/arc101/tasks/arc101_a

考察過程

1. 最適な動きを考えてみると、負に行って正に行って終えるか、正に行って負に行って終えるのが最適
2. どれだけ負に行くかであるが、負のろうそくをi個経由した場合は正のろうそくをK-i個通る必要がある
3. iを固定するとO(1)で必要な移動量がわかるので、iを全探索すればいい

解法

https://beta.atcoder.jp/contests/arc101/submissions/3081172

配列Xをそのまま使わず、正prと0以下miに分けて使う。
prとmiは最初に0を入れておき、miの方は-X[i]で入れてソートしておく。
これで、
pr[i] := 原点から正の方向にi個ろうそくを通過するのにかかる時間
mi[i] :=原点から負の方向にi個ろうそくを通過するのにかかる時間
が得られる（最初に0を入れておくのはpr[0]とmi[0]を用意するため）。
負の方向でi個ろうそくを通って、正の方向にK-i個ろうそくを通るとすると、
負の方向は往復の時間がかかるため、必要な時間はmi[i]*2+pr[K-i]となる。
これでiを全探索して、必要な時間の最小値を求める。
負の方向移動して、正の方向移動する方も試そう。

int N, K, X[101010];
vector<int> mi, pr;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i];
 
    mi.push_back(0);
    pr.push_back(0);
    rep(i, 0, N) {
        if (X[i] <= 0) mi.push_back(-X[i]);
        else pr.push_back(X[i]);
    }
    sort(all(mi));
    sort(all(pr));
 
    int n = mi.size();
    int m = pr.size();
    
    int ans = inf * 2;
    rep(i, 0, n) {
        int j = K - i;
        if (0 <= j and j < m) chmin(ans, mi[i] * 2 + pr[j]);
    }
    rep(i, 0, m) {
        int j = K - i;
        if (0 <= j and j < n) chmin(ans, pr[i] * 2 + mi[j]);
    }
    cout << ans << endl;
}