A34375. 金箍棒
填空题
困难
知识点
题目描述
金箍棒
题目描述
淘气的悟空变出了N根高度各不相同的金箍棒（1≤高度≤1000），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短1个高度或者变长1个高度。
现在悟空想通过施法将K（K≤N）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使K根相邻的金箍棒高度变为相同。
例如：N=3，K=2，3根金箍棒初始高度分别为：3，6，1。
第一次对高度为3金箍棒施法变长1个高度，变为4；
第二次对高度为6金箍棒施法变短1个高度，变为5；
第三次对高度为4金箍棒施法变长1个高度，变为5；
2根相邻的金箍棒高度变为相同，最少施法3次。
输入描述
第一行输入两个正整数N，K (1≤K≤N≤10000)，N表示金箍棒的根数，K表示需要将K根相邻的金箍棒高度变为相同，两个整数之间以一个空格隔开
第二行输入N个各不相同的正整数 (1≤正整数≤1000)，表示N根金箍棒的初始高度，N个整数之间以一个空格隔开
输出描述
输出一个整数，表示悟空最少需要施法几次可以使K根相邻的金箍棒高度变为相同
样例输入
3 2
3 6 1
样例输出
3
参考答案
// 参考代码1
#include <bits/stdc++.h>
#define N 10005
using namespace std;
int a[N];
int sum[N];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
int ans = 0x3f3f3f3f;
for (int i = 1; i + k - 1 <= n; i++) {
int aver = (sum[i + k - 1] - sum[i - 1] + k - 1) / k;
int res = 0;
for (int j = i; j < i + k; j++) {
res += abs(aver - a[j]);
}
ans = min(ans, res);
}
cout << ans << endl;
return 0;
}
上一题
下一题