已经用了堆排序和俩个队列,但是第四个样例还是tle,气晕了,来个大佬救我
查看原帖
已经用了堆排序和俩个队列,但是第四个样例还是tle,气晕了,来个大佬救我
1003129
a2651880146楼主2023/7/22 21:25

代码如下。用的是c++,帮忙看看,谢谢

#include<bits/stdc++.h>
#include<queue>
using namespace std;
long long b[100100];
int main(){
    queue<long long> s1,s2;
    long long n;
    cin>>n;
    long long aa[n];
    for(long long i=0;i<n;i++){
        cin>>aa[i];
    }
    for(int i=0;i<n;i++){
        b[aa[i]]++;
    }
    for(int i=1;i<=100000;i++){
        if(b[i]!=0){
            for(int j=1;j<=b[i];j++){
            s1.push(i);
            }
        }
    }
    long long ans=0;
    for(long long i=0;i<n-1;i++){
        if(s1.empty()){
            long long a=s2.front();
            s2.pop();
            long long b=s2.front();
            s2.pop();
            long long c=a+b;
            ans+=c;
            s2.push(c);
            continue;
        }
        if(!s2.empty()){
            if(s1.front()<=s2.front()){
                long long a=s1.front();
                s1.pop();
                if(!s1.empty()&&s1.front()<=s2.front()){
                    long long b=s1.front();
                    s1.pop();
                    long long c=a+b;
                    ans+=c;
                    s2.push(c);
                    continue;
                }
                if(s1.empty()||s1.front()>s2.front()){
                    long long b=s2.front();
                    s2.pop();
                    long long c=a+b;
                    ans+=c;
                    s2.push(c);
                    continue;
                }
            }
            if(s1.front()>s2.front()){
                long long a=s2.front();
                s2.pop();
                if(!s2.empty()&&s2.front()<=s1.front()){
                long long b=s2.front();
                s2.pop();
                long long c=a+b;
                ans+=c;
                s2.push(c);
                continue;
                }
                if(s2.empty()||s2.front()>s1.front()){
                    long long b=s1.front();
                    s1.pop();
                    long long c=a+b;
                    ans+=c;
                    s2.push(c);
                    continue;
                }
            }
        }
        if(s2.empty()){
            long long a=s1.front();
            s1.pop();
            long long b=s1.front();
            s1.pop();
            long long c=a+b;
            ans+=c;
            s2.push(c);
            continue;
        }
    }
    cout<<ans;
    return 0;
}
2023/7/22 21:25
加载中...