按照我不一定对的计算，我AC的算法比TLE的复杂度更高

P1923 【深基9.例4】求第 k 小的数

zhutier @ 2023-02-02 13:24:21

这是60分代码，最后两个点tle了，用的是堆（因为想到了对顶堆），复杂度理论上是O(nlogn),n=5000000

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
priority_queue<int> q;
int n,k,cnt;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        int tmp;
        scanf("%d",&tmp);
        if(cnt<=k){
            q.push(tmp);
            cnt++;
        }
        else{
            if(tmp<q.top()){
                q.pop();
                q.push(tmp);
            }
        }
    }
    printf("%d",q.top());
    return 0;
}

这是最后AC的代码，对第k小数二分法O(logm)，然后O(n)遍历是否满足条件，复杂度是O(nlogm),n=5000000,m=10^9

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int q[5000007];
int n,k,cnt,l,r,mid;
bool judge(int x){
    int ans=0;
    for(int i=0;i<n;i++){
        if(q[i]<=x) ans++;
        if(ans>=k+1) return 1;//太大了或者刚好 
    }
    return 0;//太小了 
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    l=1;r=1000000000;
    mid=(l+r)>>1;
    while(l<r){
        mid=(l+r)>>1;
        //printf("mid=%d\n",mid);
        if(judge(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",r);
    return 0;
}

是我算的有问题吗QAQ

by Sincerin @ 2023-02-02 13:37:11

第二个的遍历跑不满 \Theta(n) 吧？

by Dr_Gilbert @ 2023-02-02 13:43:25

@zhutier 计算没有问题，数据没卡这个。。

按以下数据生成器，即可卡到 2s+

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);cout.tie(nullptr);
    int n=5e6,k=5e6;
    cout<<n<<' '<<k<<endl;
    for (int i=1;i<=n;i++){
        cout<<(int)1e9<<' ';
    }cout<<endl;return 0;
}

by Sincerin @ 2023-02-02 13:47:17

然后第一个 n=5 \times 10^6，\log_2 n \approx 23，算上单次 \log n 的pop和push整体时间复杂度已经在 2.3 \times 10^8 左右（？）

by Sincerin @ 2023-02-02 13:50:43

@Sincerin 然后我写的priority_queue开 \operatorname{O2} 能快两倍，实测你这个开了也可过（最慢点 600\operatorname{ms}）

by zhutier @ 2023-02-03 10:26:13

@Dr_Gilbert 好嘞 谢谢你

by zhutier @ 2023-02-03 10:27:40

@Sincerin 可能确实是没卡这个

by zhutier @ 2023-02-03 10:29:14

@Sincerin 应该就每循环一次对应一个push或者pop，然后5*10^6*23这样？

|