蒟蒻TLE了,代码在线求调

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

SCma @ 2023-01-15 21:54:36

#include<bits/stdc++.h>
using namespace std;
int tick,hunt,ans;
int a[5000005];
void merge_sort(int l,int r){
    if(l==r){
        ans=a[l];
        return;
    }

    int i=l,j=r,mid=a[(l+r)/2];
    do{
        while(a[j]>mid) j--;
        while(a[i]<mid) i++;
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(hunt<=j) merge_sort(l,j);
    else if(i<=hunt) merge_sort(i,r);
    else merge_sort(j+1,i-1);
}
int main(){
    cin.tie();
    cout.tie();
    cin >> tick >> hunt; 
    for (int i=0;i<tick;i++) cin >> a[i];
    merge_sort(0,tick-1);
    cout << ans;
}

by Killer_joke @ 2023-01-15 22:00:06

ios::sync_with_stdio(false);

在输入输出前加上这句


by Killer_joke @ 2023-01-15 22:03:32

@SCma cin/cout的效率在不关闭流同步的时候很低 不适合大规模输入输出 关闭流同步后速度大幅加快通常比scanf/printf更快

关闭同步:

ios::sync_with_stdio(false);
//关闭C系列输出输出与C++输入输出的同步,同时使用可能导致顺序问题
cin.tie(nullptr);
//关闭cin与cout的流同步
//cout.tie(nullptr);一般是无效果的,因为cout默认没有与任何流通过tie绑定

by SCma @ 2023-01-16 16:04:00

谢谢


|