Codeforces 363B - Fence

題意:

Polycarpus家門前有個圍欄，由n個寬度相同的木板組成，第i個木板高度為h，Polycarpus買了一台寬度為k的鋼琴，他希望他希望拆掉連續k個木板使鋼琴能搬到家裡，而越高的木板拆除越費力，所以他希望找出最省力位置移除木板，也就是說找出某個木板的位置，向右k-1個木板高度相加會是「最小」的。
(圍欄是一個面，而不是環繞的; 木板的位置是1~n)

思路:

從第一個位置開始將k個木板的高度加總，紀錄高度與位置，每下一個位置，減去上個位置的木板加上下個木板，比較高度，較低的一方紀錄高度與位置，重複到n-k-1的位置，印出被記錄的位置就是答案。

程式碼:

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

	int main ()
	{
	int n, k, mini = 1e+9, ans = 0;
	cin >> n >> k;

	int arr[n+1] = {0};

	for (int i = 0;i < n;i++)
	{
	cin >> arr[i];
	}

	int num = 0;
	for (int i = 0;i < k;i++)
	{
	num += arr[i];
	}
	mini = num;
	ans = 1;

	for (int i = 1;i <= n-k;i++)
	{
	num = num + arr[i+k-1] - arr[i-1];
	if (mini > num)
	{
	mini = num;
	ans = i+1;
	}
	}

	cout << ans << endl;

	return 0;
	}

view raw Codeforces 363B.cpp hosted with ❤ by GitHub