2023年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第3题）-智慧文博士

2023年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第3题）

第3题

#include<vector>#include<algorithm>#include<iostream>usingnamespacestd;boolf0(vector<int>&a,intm,intk){ints=0;for(inti=0,j=0;i<a.size();i++){while(a[i]-a[j]>m)j++;s+=i-j;}returns>=k;}intf(vector<int>&a,intk){sort(a.begin(),a.end());intg=0;inth=a.back()-a[0];while(g<h){intm=g+(h-g)/2;if(f0(a,m,k)){h=m;}else{g=m+1;}}returng;}intmain(){intn,k;cin>>n>>k;vector<int>a(n,0);for(inti=0;i<n;i++){cin>>a[i];}cout<<f(a,k)<<endl;return0;}

假设输入总是合法的且1 ≤ a i ≤ 10 8 , n ≤ 10000 , 1 ≤ k ≤ n ( n − 1 ) / 2 1≤a_i≤10^8,n≤10000,1≤k≤n(n−1)/21≤ai≤108,n≤10000,1≤k≤n(n−1)/2，完成下面的判断题和单选题:

判断题

将第 24 行的m改为m - 1，输出有可能不变，而剩下情况为少 11。（）
A. 正确 B. 错误
将第 22 行的g + (h - g) / 2改为(h + g) >> 1，输出不变。（）
A. 正确 B. 错误
当输入为5 7 2 -4 5 1 -3，输出为5。（）
A. 正确 B. 错误

单选题

设 a数组中最大值减最小值加 1为 A，则f函数的时间复杂度为（）。
A. O(nlog⁡A) B. O(n2 ^22log⁡A) C. O(nlog⁡(nA)) D. O(nlog⁡n)
将第 10行中的>替换为>=，那么原输出与现输出的大小关系为（）。
A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对.
当输入为5 8 2 -5 3 8 -12，输出为（）。
A.13B.14C.8D.15

判断题答案与解析

正确（A）
- 将第24行的m改为m - 1，二分查找在满足条件时上界变为m-1。若正确答案为0，输出不变；否则输出比正确答案少1。因此说法正确。
正确（A）
- g + (h - g) / 2与(h + g) >> 1在数学上等价，且输入值在int范围内，不会溢出。因此输出不变。
正确（A）
- 输入数组排序后为[-4, -3, 1, 2, 5]，所有差值从小到大排序为[1, 1, 3, 4, 4, 5, 5, 6, 8, 9]，第7小的差值为5，程序输出5，正确。

单选题答案与解析

C. O(nlog⁡(nA))
- 函数f先排序，时间复杂度O(n log n)。二分查找范围大小为A（最大值减最小值加1），每次迭代调用f0为O(n)，二分次数O(log A)。总时间复杂度为O(n log n + n log A) = O(n log(nA))。
B. 一定小于等于且不一定小于
- 原程序输出第k小的差值ans。修改后，新程序输出ans2：
  - 若ans < max_diff，则ans2 = ans + 1；
  - 若ans = max_diff，则ans2 = ans。
- 因此原输出一定小于等于新输出，且可能相等（当ans为最大差值时）。
B. 14
- 输入数组排序后为[-12, -5, 2, 3, 8]，所有差值从小到大排序为[1, 5, 6, 7, 7, 8, 13, 14, 15, 20]，第8小的差值为14，程序输出14。

专栏推荐：信奥赛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;}

2023年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第3题）