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