U5398 改数(num)
题目背景
又是一年NOIP，科学馆的五楼：“我们看下这道题,我们来模拟一下…2,3,5,7,12…这其实就是一个a[i+1]-a[i]=i的序列……”那熟悉的凌波教鞭，熟悉的憨厚的声音，那熟悉的...哦，还有那熟悉的来自未来某位神牛的发言：“老师，好像有个数写错了……”
题目描述
给出一个长度为n的整数序列a，你能改动最少的数，使之满足a[i+1]-a[i]=i(1<=i<n)么?
输入输出格式
输入格式：
输入第一行包含一个整数n
第二行包含n个整数，分别表示a[1]到a[n]。
输出格式：
输出一个整数，表示最少改多少个数。
输入输出样例
输入样例#1：
5
1 2 4 5 11
输出样例#1：
1
说明
对于30%的数据N<=1000
对于100%的数据1<=N<=100000
输入的其他数据的绝对值均小于等于109
AC代码+题解：
/*
一种想法是可以枚举每一个数，将它固定，然后根据固定的数求出别的数，更新答案；这样是O(n^2)的；
根据这个理论，可以将每一个数固定，然后直接求出a1，看那个a1相同的次数最多，那个就是答案。
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 100010
using namespace std;
int a[N],num[N],zh1[N],n;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
num[i]=num[i-]+i-;
zh1[i]=a[i]-num[i];
}
sort(zh1+,zh1+n+);
int tot=,p=,ans;
for(int i=;i<=n;i++){
if(zh1[i]!=zh1[i-]){
if(p>tot)tot=p,ans=zh1[i-];
p=;
}
else p++;
}
if(p>tot) ans=zh1[n];
tot=;
for(int i=;i<=n;i++) if(a[i]!=ans+num[i])tot++;
printf("%d",tot);
return ;
}