小y的序列

小y的考试

https://ac.nowcoder.com/acm/contest/7780/A

这个稍微想想就会发现可以这么做

枚举每一个数当作正确序列的一点,就可以知道此时序列有多少需要改变

这样枚举,检验是

考虑只检验第一个数,那么后续的每一个数为了迎合第一个数都有一个预期值

那么对于以第一个数作为标准来算,所有需要与预期值相差为才是正确的

那么当检验第二个数时,如果比预期值大1,说明需要比预期值大才行

所以,可以开一个来保存第一个数的预期值,然后一直取即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int a[maxn],b[maxn],vis[maxn],n;
map<int,int>mp;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    int ans=n,k=a[1],temp=1;
    mp[0]++;
    for(int i=2;i<=n;i++)
    {
        k+=i-1;
        b[i]=k;
        mp[k-a[i]]++;
    }
    ans=min(ans,n-mp[0]);
    for(int i=2;i<=n;i++)
    {
        ans=min( ans,n-mp[b[i]-a[i]]);
    }
    cout << ans;
}
全部评论

相关推荐

把球:这个听过,你加了就会发现是字节的hr
点赞 评论 收藏
分享
10-15 03:05
门头沟学院 Java
CADILLAC_:凯文:我的邮箱是死了吗?
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务