zhoukangyang @ 2020-03-28 10:20:05
#include<bits/stdc++.h>
#define mian main
using namespace std;
int a[5000001],k,tot,x,suma,sumb,sumc,sooke;
int mian() {
srand((int)time(0));
scanf("%d%d",&tot,&k),k++;
for(int i = 1; i <= tot; i++) scanf("%d",&a[i]);
while(19260817) {
x=rand()%tot+1,suma=sumb=sumc=sooke=0;
for(int i = 1; i <= tot; i++) {
if(a[i]< a[x]) suma++;
if(a[i]==a[x]) sumb++;
if(a[i]> a[x]) sumc++;
}
if(suma<k&&suma+sumb>=k) {
printf("%d\n",a[x]);
return 0;
}
if(suma>=k) {
suma=0;
for(int i = 1; i <= tot; i++) if(a[i]<a[x]) ++suma,a[suma]=a[i];
tot=suma;
continue;
}
sumc=0;
for(int i = 1; i <= tot; i++) if(a[i]<a[x]) ++sumc,a[sumc]=a[i];
tot=sumc,k-=suma+sumb;
}
return 0;
}
rt
by zhoukangyang @ 2020-03-28 10:20:45
禁止
by Karrγ5307 @ 2020-03-28 10:23:32
by UnyieldingTrilobite @ 2020-03-28 10:24:30
是nth_element不够香吗
by 警策看取 @ 2020-03-28 10:27:18
sort+O2+快读不香非要手写……
by zhoukangyang @ 2020-03-28 10:27:44
@return20071007 我们老师讲了O(n)瓶颈生成树不能用stl
by zhoukangyang @ 2020-03-28 10:28:51
现在打正解的人那么少吗
by xhQYm @ 2020-03-28 10:31:18
@zhoukangyang monkey排序正解
by UnyieldingTrilobite @ 2020-03-28 10:31:20
@zhoukangyang IEE瓶颈生成树和你这题有什么关系
by Karrγ5307 @ 2020-03-28 10:31:29
您这题用O(n)瓶颈生成树跟A+B用模拟退火差不多
by Karrγ5307 @ 2020-03-28 10:31:40
@zhoukangyang