けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 107 C - Candles (ARC 101 C) (緑色, 300 点)

問題概要

N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。

解法

K 個の連続する区間で考えればよい。区間を決めると、次のいずれの行動をとるべきかはすぐに決められる

  • 原点から最初に負の方向に行き、左端に到達したら右端へ向かう
  • 原点から最初に正の方向に行き、右端に到達したら左端へ向かう

コード

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<long long> x;

int main() {
    cin >> N >> K;
    x.resize(N); for (int i = 0; i < N; ++i) cin >> x[i];
    long long res = 1LL<<60;
    for (int i = 0; i + K - 1 < N; ++i) {
        long long left = x[i], right = x[i + K - 1];
        res = min(res, min(abs(left), abs(right)) + right - left);
    }
    cout << res << endl;
}