- 2026-10-17
求卡
- @ 2026-10-17 11:34:31
求排序以下部分的复杂度证明,或者你能卡掉这份代码的话。(可能和均摊有关,但是我不会证明)
#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 条评论
目前还没有评论...