RE求助

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;
}

by xhQYm @ 2020-03-28 10:31:41

monkey排序运气好O(1)

by zhoukangyang @ 2020-03-28 10:32:12

@return20071007 瓶颈O(n)就是用这种方法啊

by zhoukangyang @ 2020-03-28 10:41:14

#include<bits/stdc++.h>
#define mian main
using namespace std;
int a[50000001],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(1) {
        cout<<tot<<" "<<k<<endl;
        x=rand()%tot+1,sooke=a[x],suma=sumb=sumc;
        for(int i = 1; i <= tot; i++) {
            if(a[i]< sooke) suma++;
            if(a[i]==sooke) sumb++;
            if(a[i]> sooke) 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]<sooke) ++suma,a[suma]=a[i];
            tot=suma;
            continue;
        }
        sumc=0;
        for(int i = 1; i <= tot; i++) if(a[i]>sooke) ++sumc,a[sumc]=a[i];
        tot=sumc,k-=suma+sumb;
    }
    return 0;
}

by zhoukangyang @ 2020-03-28 10:43:48

@return20071007 已AC(大雾

#include<bits/stdc++.h>
#define mian main
using namespace std;
int a[50000001],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(1) {
        x=rand()%tot+1,sooke=a[x],suma=sumb=sumc=0;
        for(int i = 1; i <= tot; i++) {
            if(a[i]< sooke) suma++;
            if(a[i]==sooke) sumb++;
            if(a[i]> sooke) 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]<sooke) ++suma,a[suma]=a[i];
            tot=suma;
            continue;
        }
        sumc=0;
        for(int i = 1; i <= tot; i++) if(a[i]>sooke) ++sumc,a[sumc]=a[i];
        tot=sumc,k-=suma+sumb;
    }
    return 0;
}