关于优先队列没跑过sort ??时间复杂度

回复帖子

@独赏烟花笑 2021-05-04 21:30 回复

两边代码基本一样的,就结构体那边重载的不一样,想不明白优先队列咋被卡超时了,小白求救 这边是ac代码

#include <iostream>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define max 1000005
int n; 
long long k[max];
long long mvl,nmvl;
struct Node{
    long long value;
    int index;
}node[max];
bool cmp(Node a,Node &b){
    return a.value<b.value;
}
int main(int argc, char** argv) {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>k[i];
    mvl=k[1];
    for(int i=2;i<=n;i++){
        if(k[i]*i>mvl)
            mvl=k[i]*i;
    }
    for(int i=1;i<=n;i++){
        node[i].index=i;
        node[i].value=k[i];
    }
    sort(node+1,node+n+1,cmp);
    int maxpos=node[n].index;
    nmvl=0;
    for(int i=n-1;i>=1;i--){
        long long val=node[i].value;
        int ind=node[i].index;
        if(val*(maxpos+ind)>nmvl)
            nmvl=val*(maxpos+ind);
        if(ind>maxpos)maxpos=ind;
    }
    if(mvl>nmvl)
        cout<<mvl;
    else cout<<nmvl;
    return 0;
}

这边就是被卡的代码了

#include <iostream>
#include <queue>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define max 1000005
int n; 
long long k[max];
long long mvl,nmvl;
struct node{
    long long value;
    int index;
    bool operator<(const node &n)const{
        return value<n.value;
    }
};
priority_queue<node>q;
int main(int argc, char** argv) {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>k[i];
    mvl=k[1];
    for(int i=2;i<=n;i++){
        if(k[i]*i>mvl)
            mvl=k[i]*i;
    }
    for(int i=1;i<=n;i++){
        q.push((node){k[i],i});
    }
    int maxpos=q.top().index;
    q.pop();
    nmvl=0;
    while(!q.empty()){
        long long val=q.top().value;
        int ind=q.top().index;
        if(val*(maxpos+ind)>nmvl)
            nmvl=val*(maxpos+ind);
        if(ind>maxpos)maxpos=ind;
        q.pop();    
    }
    if(mvl>nmvl)
        cout<<mvl;
    else cout<<nmvl;
    return 0;
}
@_Anchor  2021-05-04 22:01 回复 举报

快排是小常数log,堆排大常数,为什么要堆排不快排啊...而且快排内部实现好像特别高级,结合了各种排序。

@Tsukimaru 2021-05-05 07:53 回复 举报

@独赏烟花笑 举个例子:

for(int i=1; i<=n; i++)
    for(int j=1; j<=10; j++)
        sum += i + j;

for(int i=1; i<=n; i++)
    sum += 10 * i + 55;

这两个片段的复杂度都是 $O(n)$,但是前者比后者多了约 $10$ 倍的常数,所以跑得会更慢。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。