提交多次TLE

TLE_Forever @ 2020-07-30 10:06:46

#include<iostream>
#include<algorithm>
#define MAXN 5000000
using namespace std;
int n,k,a[MAXN],cnt=0;
void QuickSort(int l,int r) {
    int i=l,j=r,mid=a[(l+r)/2];
    do{
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j) {
            swap(a[i],a[j]);
            i++; j--;
        }
    }while(i<=j);
    if(l<j) QuickSort(l,j);
    if(i<r) QuickSort(i,r);
}
int main() {
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    QuickSort(0,n-1);
    for(int i=0;i<=k;i++)
        if(i==k) cout<<a[i]<<endl;
    return 0;
}

by 云浅知处 @ 2020-07-30 10:11:47

复杂度假的，你要过了才奇怪。

by H_D_NULL @ 2020-07-30 10:12:29

还是用sort吧。。。手写快读似乎用处不大

by xiaozeyu @ 2020-07-30 10:17:15

刚做这道，直接sort要开O_2，不然过不了

For(i,1,n)
    a[i]=read();
sort(a+1,a+n+1);
printf("%lld",a[k+1]);

正解是要用STL的

nth_element(数组名,数组名+第k小元素,数组名+元素个数)

nth_element(a,a+k,a+n);

只不过有人发现可以O_2sort

by xiaozeyu @ 2020-07-30 10:19:59

把$

cin

改成快读，

cout

改成

printf

sjy快读快输

by TLE_Forever @ 2020-07-30 10:21:27

@xiaozeyu 快读怎么改？

by xiaozeyu @ 2020-07-30 10:23:43

我的代码： 记得开(O_2)

#include<bits/stdc++.h>
#define For(i,a,b) for(register long long i=a;i<=b;i++)
#define Rep(i,a,b) for(register long long i=a;i>=b;i--)
using namespace std;
inline long long read()
{
    char c=getchar();long long x=0;bool f=0;
    while(!isdigit(c))f^=!(c^45),c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;return x;
}
long long n,k,a[5000010];
int main()
{
    n=read();k=read();
    For(i,1,n)
        a[i]=read();
    sort(a+1,a+n+1);
    printf("%lld",a[k+1]);
}

by TLE_Forever @ 2020-07-30 10:35:53

@xiaozeyu 这是什么原理？

by TLE_Forever @ 2020-07-30 10:36:25

@xiaozeyu 我尝试把快读嵌套到我的代码里没有用

by xiaozeyu @ 2020-07-30 10:46:44

单个读入字符要比读入数字快得多

以字符的形式读入，然后自己计算出数字

在计算出数字方面，用位运算之类的将数字转化更快

getchar()为读入单个字符

while(!isdigit(c))f^=!(c^45),c=getchar();

这个就是判断负号

x=(x<<1)+(x<<3)+(c^48);

就是用位运算更快达到

x*10；
c-='0'；

的目的

有时候，比如字符串与数字贴在一起时会吃掉字符串一直错，例如P1928 外星密码不能快读，

还有题目是有很多空格也不行，

另外有些特殊读入比如有‘/'表分数的时候别用，比如P1572 计算分数,

在这个基础上，还有小数快读：

inline double readb(){
    char c=getchar();double x=0;bool f=0;
    while(!isdigit(c))f^=!(c^45),c=getchar();
    while(isdigit(c))x=x*10+(c^48),c=getchar();
    if(!(c^46)){
        double t=1;c=getchar();
        while(isdigit(c))t/=10,x+=t*(c^48),c=getchar();
    }if(f)x=-x;return x;
}
inline int read(){
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    return x;
}

by xiaozeyu @ 2020-07-30 10:47:21

基本快读的使用：

n=read();k=read();
    For(i,1,n)
        a[i]=read();