2022年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）

2022年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）

第1题

（归并第 k 小）已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严 格单调递增），并且给定正整数 k（1≤k≤2n），求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。

试补全程序。

#include<bits/stdc++.h>usingnamespacestd;intsolve(int*a1,int*a2,intn,intk){intleft1=0,right1=n-1;intleft2=0,right2=n-1;while(left1<=right1&&left2<=right2){intm1=(left1+right1)>>1;intm2=(left2+right2)>>1;intcnt=①;if(②){if(cnt<k)left1=m1+1;elseright2=m2-1;}else{if(cnt<k)left2=m2+1;elseright1=m1-1;}}if(③){if(left1==0){returna2[k-1];}else{intx=a1[left1-1],④;returnstd::max(x,y);}}else{if(left2==0){returna1[k-1];}else{intx=a2[left2-1],⑤;returnstd::max(x,y);}}}

1. ①处应填（）

   A. (m1 + m2) * 2

   B. (m1 - 1) + (m2 - 1)

   C. m1 + m2

   D. (m1 + 1) + (m2 + 1)

2. ②处应填（）

   A. a1[m1] == a2[m2]

   B. a1[m1] <= a2[m2]

   C. a1[m1] >= a2[m2]

   D. a1[m1] != a2[m2]

3. ③处应填（）

   A. left1 == right1

   B. left1 < right1

   C. left1 > right1

   D. left1 != right1

4. ④处应填（）

   A. y = a1[k - left2 - 1]

   B. y = a1[k - left2]

   C. y = a2[k - left1 - 1]

   D. y = a2[k - left1]

5. ⑤处应填（）

   A. y = a1[k - left2 - 1]

   B. y = a1[k - left2]

   C. y = a2[k - left1 - 1]

   D. y = a2[k - left1]

答案

1. ① C
2. ② B
3. ③ C
4. ④ C
5. ⑤ A

题解

算法通过二分两个数组的当前范围，每次比较两个中位数a1[m1]和a2[m2]。

• cnt = m1 + m2表示两个数组中位于当前中位数之前的元素总数（不包括中位数本身）。
• 若a1[m1] <= a2[m2]，则进入第一个分支：
  • 若cnt < k，说明a1[m1]及其之前的元素均小于第k小，故可丢弃a1的左半部分（left1 = m1 + 1）。
  • 否则，第k小一定不大于a1[m1]，故可丢弃a2的右半部分（right2 = m2 - 1）。
• 若a1[m1] > a2[m2]，则进入对称分支。

循环直至一个数组的范围为空。若a1为空（left1 > right1），则第k小为max(a1[left1 - 1], a2[k - left1 - 1])；若a2为空，则为max(a2[left2 - 1], a1[k - left2 - 1])。该算法时间复杂度为O(log n)。

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}