RE求助

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

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

禁止sort人人有责


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


| 下一页