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

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

第 1 题

（序列合并）有两个长度为 N的单调不降序列 A和 B，序列的每个元素都是小于10 9 10^9109的非负整数。在 A和 B中各取一个数相加可以得到 N2 ^22个和，求其中第 K小的和。上述参数满足 N≤10 5 10^5105和 1≤K≤N 2 N^2N2。

#include<iostream>usingnamespacestd;constintmaxn=100005;intn;longlongk;inta[maxn],b[maxn];int*upper_bound(int*a,int*an,intai){intl=0,r=___①___;while(l<r){intmid=(l+r)>>1;if(___②___){r=mid;}else{l=mid+1;}}return___③___;}longlongget_rank(intsum){longlongrank=0;for(inti=0;i<n;++i){rank+=upper_bound(b,b+n,sum-a[i])-b;}returnrank;}intsolve(){intl=0,r=___④___;while(l<r){intmid=((longlong)l+r)>>1;if(___⑤___){l=mid+1;}else{r=mid;}}returnl;}intmain(){cin>>n>>k;for(inti=0;i<n;++i)cin>>a[i];for(inti=0;i<n;++i)cin>>b[i];cout<<solve()<<endl;}

1. ① 处应填（ ）？
   A.an-a
   B.an-a-1
   C.ai
   D.ai+1
2. ② 处应填（ ）？
   A.a[mid] > ai
   B.a[mid] >= ai
   C.a[mid] < ai
   D.a[mid] <= ai
3. ③ 处应填（ ）？
   A.a+l
   B.a+l+1
   C.a+l-1
   D.an-l
4. ④ 处应填（ ）？
   A.a[n-1]+b[n-1]
   B.a[n]+b[n]
   C.2 * maxn
   D.maxn
5. ⑤ 处应填（ ）？
   A.get_rank(mid) < k
   B.get_rank(mid) <= k
   C.get_rank(mid) > k
   D.get_rank(mid) >= k

题解：

本题要求从两个长度为 (N) 的单调不降序列 (A) 和 (B) 中各取一个数相加，得到 (N2 ^22) 个和，求第 (K) 小的和。解题思路是利用二分答案，统计有多少个和不超过给定的值 (sum)，然后通过二分找到最小的 (sum) 使得不超过它的和的数量至少为 (K)。

• ①：在upper_bound函数中，需要确定二分查找的右边界，即数组的长度。由于参数a和an分别指向数组起始和结束的下一个位置，因此长度应为an - a。选A
• ②：upper_bound函数的目标是找到第一个大于ai的元素，因此在二分过程中，当a[mid] > ai时，应将右边界移动到mid，否则左边界移动到mid + 1。选A
• ③：二分查找结束后，左边界l即为第一个大于ai的元素的索引，因此返回指针a + l。选A
• ④：二分答案的右边界应设为可能的最大和，即 (a[N-1] + b[N-1])。选A
• ⑤：在二分答案过程中，若get_rank(mid)（即不超过mid的和的数量）小于 (K)，说明mid太小，需要增大左边界；否则减小右边界。因此条件为get_rank(mid) < k。选A

专栏推荐：信奥赛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 点击跳转

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;}