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;
}
快排都能超时???
#%@&()#%)()%¥!#%……##¥$%@&我屮艸芔茻凸(艹皿艹 )
#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
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
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吸氧过