题解：P13595 『GTOI - 1B』筝

· · 题解

P13595 『GTOI - 1B』筝

解题思路

从特殊性质 a_i=i 切入，发现将相邻的两个数调至共鸣调整度之和最小，为 \lfloor \frac{n+1}{2} \rfloor。

扩展一下可以发现，差值大于 1 的两数调整至相等所花费的调整度一定大于或等于依次调整差值为 1 的两数，因此仅调整差值为 1 的两数达到要求花费的调整度之和一定最小。

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

完整代码

#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;
}