很新奇的做法,能过,0(n)复杂度
查看原帖
很新奇的做法,能过,0(n)复杂度
933281
tim2010楼主2024/10/27 09:50
#include<bits/stdc++.h>
using namespace std;
int n;
int maxn=0;
int p[100050],sz[1000050];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        maxn=max(maxn,p[i]);
        sz[p[i]]++;
    }
    int sum=n;
    for(int i=1;i<=maxn;i++){
        if(sz[i]>sz[i-1]) sz[i-1]=0;
        else sz[i]+=abs(sz[i]-sz[i-1]);
        sz[i-1]=0;
    }
    cout<<sz[maxn];
}
2024/10/27 09:50
加载中...