Candles [AtCoder Beginner Contest 107 C]

atcoder.jp

数直線上に N 個の座標がある。最初、立っている座標は x=0 である。
N 個のうち K 個の座標を訪れるとき、移動距離の総和の最小値として考えられるのはいくつか、という問題です。

訪れる K 個の座標は、連続していたほうがよいです。わざわざ1つ飛ばしに訪れて移動距離を増やすことはありません。N 個の座標のうち、連続した K 個の区間は N-K+1 個存在し、これらを全て試して移動距離が最小になるものを採用します。

K 個の連続した座標を訪れるということは、K 個の座標のうち最も左にある座標と最も右にある座標を訪れることに等しいです。このとき、最も左にある座標を先に訪れるべきか、あるいは最も右にある座標を先に訪れるべきかは、両方試してみて移動距離が少ないほうを採用します。

最も左にある座標を L 、最も右にある座標を R としたとき、それらと原点の位置関係には

・L - 0 - R
・0 - L - R
・L - R - 0

の3つが存在しますが、いずれの位置関係であっても、L を先に訪れる場合の移動距離は

・| L | + | L - R |

R を先に訪れる場合の移動距離は

・| R | + | L - R |

で求めることができます。

void solve () {

	int n = nextInt(), k = nextInt();
	int[] ar = nextIntArray(n);

	int min = maxInt;
	for (int i=0; i<n-k+1; i++) {
		int L = ar[i];
		int R = ar[i+k-1];

		int LR = Math.abs(L) + Math.abs(L-R);
		int RL = Math.abs(R) + Math.abs(L-R);
		min = Math.min(min, Math.min(LR, RL));
	}

	out.println(min);

}