牛客IOI周赛19-普及组 B-小y的序列

小y的序列

• 分析

  我这个不是正解。根据题目中的定义，我们很容易想到O(n^2)循环，即以每个a[i]为标准，求出要修改多少个。进而，

  我们可以先预处理出对于一个位置 i ，可以扩展的合法区间，然后在这些区间之间循环，减小时间复杂度。最重要的

  一步便是怀揣梦想(看代码就知道了)

• 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;

int n,ans=1e9;
int tu=0;
ll a[N],to[N],l[N];

int main()
{
    scanf("%d",&n);
    for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    int now=2,las=1;
    while(now<=n)
    {
        if(a[now]-a[now-1]!=(now-1))
        {
            to[las]=now-1;
            las=now;
        }
        now++;
    }to[las]=n;

    for (int i=1;i<=n;i=to[i]+1)
    {
        int num=l[i];ll ok=to[i]-i+1;

        for (ll j=i+1;j<=n;j=to[j]+1)
            if(a[j]-a[i]!=((j-i)*(i+j-1)/2))
            {
                tu++;
                num+=(to[j]-j+1);
                l[j]+=ok;
            }

        ans=min(ans,num);

        if(tu>=20000000) break;//人没点梦想还怎么活下去？
    }

    printf("%d\n",ans);

    return 0;
}