C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 4300K, 提交时间: 2020-10-14 20:31:28

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,ans;
map<ll,ll> mp;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		mp[a-i*(i+1)/2-1]++;
		ans = max(ans,mp[a-i*(i+1)/2-1]);
	}
	cout<<n-ans<<endl;
} 

C++ 解法, 执行用时: 47ms, 内存消耗: 3236K, 提交时间: 2021-09-12 22:50:59

#include<iostream>
#include<map>
using namespace std;
int n,m,sum=-1;
map<int,int>mp;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		m=m-i*(i-1)/2;
		mp[m]++;
		sum=max(sum,mp[m]);
	}
	cout<<n-sum<<endl;
return 0;
}

Python3 解法, 执行用时: 263ms, 内存消耗: 17364K, 提交时间: 2021-11-26 20:06:36

n=int(input())
a=list(map(int,input().split()))
d={}
m=0
for i in range(n):
    k=0
    t=a[i]-i*(i+1)//2
    if t not in d.keys():
        d[t]=1
    else:
        d[t]+=1
    m=max(m,d[t])
print(n-m)