第24题 #include <iostream>  #include <cstdlib>  using namespace std;     int n;  int d[100

1. #include <iostream> 
2. #include <cstdlib> 
3. using namespace std; 
4.   
5. int n; 
6. int d[10000]; 
7.   
8. int find(int L, int R, int k) { 
9.     int x = rand() % (R - L + 1) + L; 
10.     swap(d[L], d[x]); 
11.     int a = L + 1, b = R; 
12.     while (a < b) { 
13.         while (a < b && d[a] < d[L]) 
14.             ++a; 
15.         while (a < b && d[b] >= d[L]) 
16.             --b; 
17.         swap(d[a], d[b]); 
18.     } 
19.     if (d[a] < d[L]) 
20.         ++a; 
21.     if (a - L == k) 
22.         return d[L]; 
23.     if (a - L < k) 
24.         return find(a, R, k - (a - L)); 
25.     return find(L + 1, a - 1, k); 
26. } 
27.   
28. int main() { 
29.     int k; 
30.     cin >> n; 
31.     cin >> k; 
32.     for (int i = 0; i < n; ++i) 
33.         cin >> d[i]; 
34.     cout << find(0, n - 1, k); 
35.     return 0; 
36. } 

假设输入的 n，k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。lpr100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3）当输入的 d[i] 是严格单调递增序列时，第 17 行的“swap”的平均执行次数是（ ）lpr100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库