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

2023年信奥赛C提高组csp-s初赛真题及答案解析阅读程序第3题第3题#includevector#includealgorithm#includeiostreamusingnamespacestd;boolf0(vectorinta,intm,intk){ints0;for(inti0,j0;ia.size();i){while(a[i]-a[j]m)j;si-j;}returnsk;}intf(vectorinta,intk){sort(a.begin(),a.end());intg0;intha.back()-a[0];while(gh){intmg(h-g)/2;if(f0(a,m,k)){hm;}else{gm1;}}returng;}intmain(){intn,k;cinnk;vectorinta(n,0);for(inti0;in;i){cina[i];}coutf(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。因此说法正确。正确Ag (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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}