打卡信奥刷题（1418）用C++实现信奥 B4298 [蓝桥杯青少年组国赛 2022] 金箍棒_第五题[编程实现]金箍棒。[题目描述]淘气的悟空变出n根高度各不相同的金箍棒(

B4298 [蓝桥杯青少年组国赛 2022] 金箍棒

题目背景

为区分各种时间复杂度的做法，本题时间限制下调到 500 毫秒。

题目描述

淘气的悟空变出了 $N$ 根高度各不相同的金箍棒（$1 \\leq $ 高度 $\le 1000$），并排列成一排。悟空可以对每根金箍棒施法，让金箍棒高度变短或者变长，但每一次施法只能使一根金箍棒变短 $1$ 个高度或者变长 $1$ 个高度。

现在悟空想通过施法将 $K$（$K\le N$）根相邻的金箍棒高度变为相同，且要求施法的次数最少，请你帮助悟空计算出最少需要施法几次可以使 $K$ 根相邻的金箍棒高度变为相同。

例如：$N=3$，$K=2$，$3$ 根金箍棒初始高度分别为 $3$、$6$、$1$。

• 第一次对高度为 $3$ 的金箍棒施法变长 $1$ 个高度，变为 $4$；
• 第二次对高度为 $6$ 的金箍棒施法变短 $1$ 个高度，变为 $5$；
• 第三次对高度为 $4$ 的金箍棒施法变长 $1$ 个高度，变为 $5$；

$2$ 根相邻的金箍棒高度变为相同，最少施法 $3$ 次。

输入格式

第一行输入两个正整数 $N$、$K$（$1\le K\le N\le 10000$），$N$ 表示金箍棒的根数，$K$ 表示需要将 $K$ 根相邻的金箍棒高度变为相同，两个整数之间以一个空格隔开。

第二行输入 $N$ 个各不相同的正整数（$1\le$ 正整数$\le 1000$），表示 $N$ 根金箍棒的初始高度，$N$ 个整数之间以一个空格隔开。

输出格式

输出一个整数，表示悟空最少需要施法几次可以使 $K$ 根相邻的金箍棒高度变为相同。

输入输出样例 #1

输入 #1

3 23 6 1

输出 #1

3

C++实现

#include using namespace std;int n,k,i,s,j,a[100001],mi=2e9,b[10001];int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(i=1;i<=n;i++) cin>>a[i];for(i=1;i<=n-k+1;i++){s=0;for(j=i;j<=i+k-1;j++) b[j-i+1]=a[j];nth_element(b+1,b+(k+1)/2,b+k+1); for(j=1;j<=k;j++)s+=abs(b[(k+1)/2]-b[j]); mi=min(mi,s);}cout<<mi;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容