小y的序列
思路：
1）因为要求最小的改变次数，那么就是要从这个序列中找出最长符合a[i+1]-a[i] = i的序列，它们之间可以是不相邻的，也就是说把其他不符合这个最长的序列的元素改变使得它们满足这个序就可以了，而这个最长序列中的元素不用改变。
2）现在是要如何找到这个最长序列呢。
那我们就先找到一个符合a[i+1]-a[i]=i的一个序列，长度和题目给的序列的长度相等，我们只需要看这个序列的元素和题目给的序列对应下标的元素相差多少，假设是x，用mp[x]保存x出现的次数，也就是能组成符合序列的长度。
3）为什么这样可以呢？比如下标为i和j的元素a[i],a[j],题目给出的数是m,n,因为a[j] - a[i] = x,如果m-a[i] = n - a[j], 那两个数加上同一个数后还是等于x，序列还是符合。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#define ll long long
const int mod = 1e9+7;
using namespace std;
map<int,int>mp;
int a[100005];
int main()
{
int n,mmax = -1;
scanf("%d",&n);
for(int i = 1; i <= n; i++) a[i] = a[i - 1] + i - 1;
for(int i = 1; i <= n; i++){
int x;
scanf("%d",&x);
mmax = max(mmax,++mp[x - a[i]]);
//cout << x - a[i] << endl;
}
printf("%d\n",n - mmax);
return 0;
}
查看8道真题和解析
投递莉莉丝游戏等公司10个岗位 >