残疾人做法，全RE

Bacteria @ 2021-12-06 17:46:29

#include<bits/stdc++.h>
using namespace std;
bool a[100000000];
int main()
{
    int n,k,m,c=0,j=1;
    cin>>n>>k;
    k+=1;
    for(int i=1;i<=n;++i)
    {
        cin>>m;
        a[m]=1;
    }
    while(c!=k)
    {
        if(a[j]==1)
        c++;
        if(c==k)
        {
        cout<<j;
        break;
        }
        j++;
    }
    return 0;
}

by Galois_Field_1048576 @ 2021-12-06 17:48:08

by Bacteria @ 2021-12-06 17:48:56

@lhx1048576 这样吗...谢谢大佬

by MujicaSaki @ 2021-12-06 17:49:06

nth_element不挺好吗

捞

我也顺便捞一下我这道题的求助

by Spasmodic @ 2021-12-06 18:08:15

@Bacteria 10^9=1000000000，你只有 10^8，所以会 RE。这道题不能用这种方法（除非你用 bitset 搞）

by HeCao2008 @ 2021-12-06 18:11:16

数组越界了

by Anamnesis @ 2021-12-06 19:48:29

其实假设 bool 数组可以开到 10^9 范围而不 MLE，也还存在一些问题：

• 题目会输入重复的数字，只使用 bool 数组记录一个数是否出现而不记录出现次数，会导致 WA；
• 您的代码似乎是从 1 扫到 10^9 直到出现 k 个数，但如果所有数字都稠密地出现在区间上界附近，而不存在较小的数（比如答案就是 10^9 时），就会导致运算次数达到 10^9 级别，从而 TLE。

使用 bitset 似乎也是不太可行的……在使用 _Find_next() 函数将时空复杂度均降到 \Theta(\frac{10^9}{w}) 的情况下，如果额外使用 map 记录出现过的数字的出现次数，会因为时间复杂度多一个 \log 而 TLE，如果使用 O(1) 时间的 __gnu_pbds::gp_hash_table，会 MLE。

只能得到 60 分的代码是这样的：

const int lim = 1e9 + 1;
bitset<lim> bit;
__gnu_pbds::gp_hash_table<int, int> exmp;
int main() {
    int n = read(), k = read() + 1;
    for (int i = 1, x; i <= n; ++i)
        x = read(), bit[x] = 1, ++exmp[x];
    int cnt = 0;
    for (int i = bit._Find_first(); i < lim; i = bit._Find_next(i)) {
        cnt += exmp[i];
        if (cnt >= k) {
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}

期待有神仙提出能够 AC 的基于桶排的做法 QWQ