题目
T组数据,每次给出n(n<=1e7)个正整数,
输出从大到小第k大的数,时限1s,空间131072KB
题解
现在想想找第k大就是快排划个轴递归嘛,像线段树上二分一样
nth_element一下就好,nth_element会取出中间那个参数rank的值放在那个位置,并使左侧的比它小,右侧的比它大
在学弟的敦促下,写了一发快排的写法,只是这题由于输入数据1e7,太毒瘤了
卡掉了好几个快读的板子和快排的写法,递归快排比循环快排还是略慢一点,在快读板子的帮助下终于没T
自己写的随机取轴必被卡,实在没办法,nth_element系统优化可能有若干随机的参
代码
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int N=1e7+10;int T,n,k,aa[N];struct FastIO{FILE *fp;static const int S=1e7;typedef long long ll;int wpos;char wbuf[S];FastIO():wpos(0){}inline int xchar(){static char buf[S];static int len=0,pos=0;if(pos==len)pos=0,len=fread(buf,1,S,stdin);return buf[pos++];}inline int xuint(){int c=xchar(),x=0;while(c<=32)c=xchar();for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';return x;}inline int xint(){int s=1,c=xchar(),x=0;while(c<=32)c=xchar();if(c=='-')s=-1,c=xchar();for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';return x*s;}inline void xstring(char *s){int c=xchar();while(c<=32)c=xchar();for(;c>32;c=xchar())*s++=c;*s=0;}inline void wchar(int x){if(wpos==S)fwrite(wbuf,1,S,stdout);wbuf[wpos++]=x;}inline void wint(ll x){if(x<0)wchar('-'),x=-x;char s[24];int n=0;while(x||!n)s[n++]='0'+x%10,x/=10;while(n--)wchar(s[n]);wchar('\n');}inline void wstring(const char *s){while(*s)wchar(*s++);}~FastIO(){if(wpos)fwrite(wbuf,1,wpos,stdout),wpos=0;}}io;void sort(int l, int k, int r){if(l>=r)return;swap(aa[l],aa[(l+r)>>1]);int L=l,R=r-1,x=aa[l];while(L<R){while(L<R&&aa[R]>=x)R--;aa[L]=aa[R];while(L<R&&aa[L]<=x)L++;aa[R]=aa[L];}aa[L]=x;int left=L-l+1;if(left>k)sort(l,k,L);if(k>left)sort(L+1,k-left,r);}int main(){int T;T=io.xint();while(T--){n=io.xint(),k=io.xint();for(int i=0;i<n;++i)aa[i]=io.xint();sort(0,n+1-k,n);//nth_element(aa,aa+n-k,aa+n);io.wint(aa[n-k]);}return 0;}
后续
思路来源
/p/e750b0512881
碰到一模一样的题,要确定一个2e6数组的中位数,
但是这个题交原来那个题的代码,怎么交怎么TLE,卡不过去,
于是,根据油井问题,对这个题快排部分进行了重写,
等CSU网站好了之后,打算重新交一发,看看能不能过
思路
首先,对[l,r]区间随机一个位置p,把p和l位置的数互换,防止被卡(然而实际还是被卡了)
然后用快排的思想把大于a[p]的数都放在右,小于a[p]的数都在左,
然后看p在[l,r]区间里是第几大,计左半部分(含轴)的长度为len=p-l+1
若k<=len去[l,p]里找第k大,否则去[p+1,r]里找第k-p大,期望意义O(n)
代码
#include<bits/stdc++.h>using namespace std;const int N=2e6+10;typedef long long ll;int T,n,k,x,y,a[N];int p(int a[],int l,int r){int x=(rand()%(r-l+1))+l;swap(a[l],a[x]);int mid=a[l],i=l,j=r;while(i!=j){while(a[j]>=mid&&i<j){j--;}while(a[i]<=mid&&i<j){i++;}swap(a[i],a[j]);}a[l]=a[j];a[j]=mid;return j;}int qs(int a[],int l,int k,int r){if(l==r){return a[l];}int mid=p(a,l,r),len=mid-l+1;//printf("l:%d k:%d mid:%d r:%d a:%d\n",l,k,mid,r,a[mid]);if(k<=len){return qs(a,l,k,mid);}else{return qs(a,mid+1,k-len,r);}}int main(){srand(time(0));scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}k=(n+1)-k;//从大到小第k 是从小到大第(n+1)-kprintf("%d\n",qs(a,1,k,n));}return 0;}
如果觉得《CSU - 2078 查找第k大(O(n)区间第k大 快排思想)》对你有帮助,请点赞、收藏,并留下你的观点哦!