問題概要
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; }