CSP-S2019的代码其实可能出锅!
本人在本地运行如下代码:
#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int d[10000];
int find(int L, int R, int k) {
int x = rand() % (R - L + 1) + L;
swap(d[L], d[x]);
int a = L + 1, b = R;
while (a < b) {
while (a < b && d[a] < d[L])
++a;
while (a < b && d[b] >= d[L])
--b;
swap(d[a], d[b]);
}
if (d[a] < d[L])
++a;
if(a>=10000){
cout<<"Yes!";
exit(0);
}
if (a - L == k)
return d[L];
if (a - L < k)
return find(a, R, k - (a - L));
return find(L + 1, a - 1, k);
}
int main() {
int k;
//cin >> n;
//cin >> k;
n=10000,k=10000;
for (int i = 0; i < n; ++i)
/*cin >> d[i];*/d[i]=rand();
cout << find(0, n - 1, k);
main();
return 0;
}
竟然输出了 yes!(震惊)
不喜麻烦告知,紫衫。