發表新討論
#45314: 請問這樣子也RE要怎麼解？


JengSwan (Jeng Swan)

學校 : 國立臺南女子高級中學
編號 : 255594
來源 : [123.252.108.9]
最後登入時間 ：
2025-03-12 14:46:47
h181. 第k大的數(hard version) | From: [101.9.36.93] | 發表日期 : 2025-02-13 19:54

#include <cstdio>

#include <algorithm>

using namespace std;

int a[1000000]

int main() {

    int n, k;

    scanf("%d", &n);

    for (int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);;

    scanf("%d", &k);

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

    printf("%d", a[n-k]);

    return 0;

}

 

發現只要用任何方法存n個數字就記憶體超出上限。如果不存n個數字，要怎麼知道第k大？n個數字輸入完才輸入k，也不能用priority_queue。

 
#45315: Re: 請問這樣子也RE要怎麼解？


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2025-02-23 20:02:20
h181. 第k大的數(hard version) | From: [122.116.111.175] | 發表日期 : 2025-02-13 20:02

#include

#include

using namespace std;

int a[1000000]

int main() {

    int n, k;

    scanf("%d", &n);

    for (int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);;

    scanf("%d", &k);

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

    printf("%d", a[n-k]);

    return 0;

}

 

發現只要用任何方法存n個數字就記憶體超出上限。如果不存n個數字，要怎麼知道第k大？n個數字輸入完才輸入k，也不能用priority_queue。



https://hackmd.io/@becaido/HyeldiNW3

可參考 p12

 

 
ZeroJudge Forum