P13595 『GTOI - 1B』筝

解题思路

从特殊性质

a_i=i

切入，发现将相邻的两个数调至共鸣调整度之和最小，为

\lfloor \frac{n+1}{2} \rfloor

。

扩展一下可以发现，差值大于

1

的两数调整至相等所花费的调整度一定大于或等于依次调整差值为

1

的两数，因此仅调整差值为

1

的两数达到要求花费的调整度之和一定最小。

把差值为

1

的两数全部看作区间，这时就可以发现原本的题目变为了一道区间覆盖问题，且所有是已经排序好的。最后只需求最少需要几个区间将整个数列覆盖就行了。

完整代码

CPP

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MAXN=1e7+9;
int n,a[MAXN],b[MAXN],f[MAXN],out,tmp,ans=1;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i),b[a[i]]=i;
	out=max(b[a[1]-1],b[a[1]+1]);
	while(1)
	{
		if(out==n)break;
		int cnt=0;
		for(int i=tmp+1;i<=out+1;i++)cnt=max(max(b[a[i]-1],b[a[i]+1]),cnt);
		tmp=out;out=cnt;ans++;
	}
	printf("%d",ans);
	return 0;
}

题解：P13595 『GTOI - 1B』筝

文章操作

P13595 『GTOI - 1B』筝

解题思路

完整代码

相关推荐

评论

题解：P13595 『GTOI - 1B』筝