题解：P13728 [GCPC 2024] Musical Mending

比较简单的数学题~~

问题提炼

题目大致是这样的：有 n 个琴键，第一个琴键为音高0，后面的琴键音高不准，你需要确保每个琴键的音高恰好比前一个琴键高 1，比后一个琴键低 1。即要调成一个以 0 开始的有序依次上升的数列，求调节的最小音量和。

思路分析

面对这样的题目，我的第一反应是将第 i 个 t 与其标准的音量值 i 求绝对值得出答案（i从0开始计），代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int main(){
	int n;
	cin>>n;
	int t[N];
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>t[i];
		ans+=abs(t[i]-i);
	} 
	cout<<ans;
	return 0;
}

但是这样只能正确输出前 3 个样例，后两个样例就不可行了。那么如何才能得到满分做法呢？不难发现，此题求的是最小值，我们可以将第一个琴键的音高看做 x ，则标准音高为 x+i-1 , 调整量 p =|t-(x+i-1)|=|(t-i+1)-x| 。为了使其调整量尽量小，则在整个数列中， x 应取中位数（不太懂的可以去看看小学奥数题中的奇点偶段数轴题），最后得出调整量之和。代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int main(){
	int n;
	cin>>n;
	int t[N];
	long long ans=0;
	for(int i=0;i<n;i++){
		cin>>t[i];
		t[i]=t[i]-i;
	} 
	sort(t,t+n);
	int mid=n/2;
	for(int i=0;i<n;i++){
		ans+=abs(t[i]-t[mid]);
	}
	cout<<ans;
	return 0;
}

别忘了一件事情，不开long long----(自觉接上，本人也是见上一面了)，那么这道题也是成功AC了！

蒟蒻第一次写题解，请见谅 to_ot

题解：P13728 [GCPC 2024] Musical Mending

文章操作

问题提炼

思路分析

相关推荐

评论

题解：P13728 [GCPC 2024] Musical Mending