什么问题???QAQ

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

strcmp @ 2021-09-19 23:51:09

一看到题目,本蒟蒻第一反应是:

大大大大大大大大大大大大大大大大大大大水题

于是编写了如下代码:

#include <iostream>
#include<algorithm>
using namespace std;
int main() {
    int n,k;
    cin >> n >> k;
    long long *a=new long long[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    cout << a[k];
    return 0;
}

然后成功TLE

快排都能超时??? #%@&()#%)()%¥!#%……##¥$%@&我屮艸芔茻凸(艹皿艹 )

我又用计数排序写了以下代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k;
int main() {
    cin >> n >> k;
    long long* a = new long long[n + 10];
    long long* b = new long long[n+10];
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    for (int i = 1; i <=n; i++) {
        cin >> a[i];
        b[a[i]] = a[i];
    }
    int sum = 0;
    unique(b, b + n);
    for (int i = 1; i <=n; i++) {
        if (b[i] != 0 && k>=0) {
            k--;
            sum++;
        }
    }
    cout << sum;
    return 0;
}

结果是: 五个测试点两个WA三个RE

请问各位神牛牪犇是什么问题QAQ!!!!!


by strcmp @ 2021-09-19 23:54:25


by omemi @ 2021-09-20 01:32:43

@wql463 最多5e6的输入,建议使用

scanf()

或者cin加上

std::ios::with_stdio(0),
std::cin.tie(0), std::cout.tie(0);

第二个计数排序,b数组是以a[i]为下标访问的,而a[i]最大1e9,不言自明。

另外,“本题的重点在于练习分治算法”

水经验没有意思的orz


by omemi @ 2021-09-20 01:38:20

@omemi 我打错了,应该是

std::ios::sync_with_stdio(0),
std::cin.tie(0), std::cout.tie(0);

另外我试过了,这样也还是会t的,这题快排应该是过不了。


by xieyikai2333 @ 2021-09-20 07:11:02

@wql463 sort() 复杂度 nlogn,能过才怪


by Zvelig1205 @ 2021-09-20 10:07:05

@wql463 吸氧呗


by 230syh @ 2021-09-20 21:14:56

@极冬寒雪 吸氧也不行,1.2s


by Zvelig1205 @ 2021-09-20 21:57:46

@230syh 我用 STL sort 和 手打 sort 都吸氧过了。


by strcmp @ 2021-12-31 22:04:31

STLsort吸氧过


|