求排序以下部分的复杂度证明,或者你能卡掉这份代码的话。(可能和均摊有关,但是我不会证明)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+720;
int n,a[N],pos[N];
bool cmp(int A,int B){
	return a[A]>a[B];
}int ans;
signed main(){
	//freopen("ex.in","r",stdin);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];pos[i]=i;
	}sort(pos+1,pos+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(a[pos[i]]==0) continue;
		int t=a[pos[i]];ans+=t;
		for(int j=pos[i]+1;j<=n;j++){
			if(t==0) break;
			if(a[j]<=t){
				t=a[j];
			}a[j]-=t;
		}t=a[pos[i]];a[pos[i]]=0;
		for(int j=pos[i]-1;j>=1;j--){
			if(t==0) break;
			if(a[j]<=t){
				t=a[j];
			}a[j]-=t;
		}
	}cout << ans;
	return 0;
}

0 条评论

目前还没有评论...