您的位置:首页 > 教育 > 培训 > CSP-S 2023 提高级 第一轮(初赛) 阅读程序(3)

CSP-S 2023 提高级 第一轮(初赛) 阅读程序(3)

2024/11/3 23:32:03 来源:https://blog.csdn.net/lq1990717/article/details/142212319  浏览:    关键词:CSP-S 2023 提高级 第一轮(初赛) 阅读程序(3)

【题目】

CSP-S 2023 提高级 第一轮(初赛) 阅读程序(3)

#include <vector>
#include <algorithm>
#include <iostream>using namespace std;bool f0(vector<int> &a, int m, int k) {int s = 0;for (int i = 0, j = 0; i < a.size(); i++) {while (a[i] - a[j] > m)j++;s += i - j;}return s >= k;
}int f(vector<int> &a, int k) {sort(a.begin(), a.end());int g = 0;int h = a.back() - a[0];while (g < h) {int m = g + (h - g) / 2;if (f0(a, m, k)) {h = m;}else {g = m + 1;}}return g;
}int main() {int n, k;cin >> n >> k;vector<int> a(n, 0);for (int i = 0; i < n; i++) {cin >> a[i];}cout << f(a, k) << endl;return 0;
}

假设输入总是合法的且 1 ≤ a i ≤ 1 0 8 1 \le a_i \le 10^8 1ai108, n ≤ 10000 n \le 10000 n10000, 1 ≤ k ≤ n ( n − 1 ) 2 1 \le k \le \frac {n(n-1)}{2} 1k2n(n1),完成下面的判断题和单选题:

判断题
1.将第 24 行的 m 改为 m - 1,输出有可能不变,而剩下情况为少 1。()
2.将第 22 行的 g + (h - g) / 2 改为 (h + g) >> 1,输出不变。()
3.当输入为 5 7 2 -4 5 1 -3,输出为 5。()

单选题
4.设 a 数组中最大值减最小值加 1 为 A,则 f 函数的时间复杂度为()。
A. O ( n log ⁡ A ) O(n \log A) O(nlogA)
B. O ( n 2 log ⁡ A ) O(n^2 \log A) O(n2logA)
C. O ( n log ⁡ ( n A ) ) O(n \log (nA)) O(nlog(nA))
D. O ( n log ⁡ n ) O(n \log n) O(nlogn)

5.将第 10 行中的 > 替换为 >=,那么原输出与现输出的大小关系为()。
A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对.

6.当输入为 5 8 2 -5 3 8 -12,输出为()。
A. 13
B. 14
C. 8
D. 15

【题目考点】

1. 二分答案

【解题思路】

int main() {int n, k;cin >> n >> k;vector<int> a(n, 0);for (int i = 0; i < n; i++) {cin >> a[i];}cout << f(a, k) << endl;return 0;
}

输入n,k,设顺序表a,输入数据到a[0]a[n-1]
输出f(a,k)的值。

int f(vector<int> &a, int k) {sort(a.begin(), a.end());int g = 0;int h = a.back() - a[0];while (g < h) {int m = g + (h - g) / 2;if (f0(a, m, k)) {h = m;}else {g = m + 1;}}return g;
}

f数组传入了顺序表a的引用,和k的值。
首先sort(a.begin(), a.end());完成对顺序表a进行升序排序。
接下来是明显的二分答案模板。
答案变量左端点g设为答案的最小值0,右端点h设为答案的最大值,为a的最后一个数值减去第一个数值。由于序列a已经升序排序,则h的初值为序列a的最大值减最小值。
该二分答案代码求的是满足条件的最小值,符合以下模板:

while(l < r)
{int mid = (l+r)/2;if(check(mid))r = mid;elsel = mid+1;
}
cout << l;//或cout << r

f0函数判断当前值m是否满足条件。

bool f0(vector<int> &a, int m, int k) {int s = 0;for (int i = 0, j = 0; i < a.size(); i++) {while (a[i] - a[j] > m)j++;s += i - j;}return s >= k;
}

s是计数变量,i和j都是顺序表a的下标,i从0到a.size()-1遍历顺序表a。
当遍历到第i元素a[i]时,只要a[i]和a[j]的差值大于m,j就增加。当循环跳出时满足a[i]-a[j] <= m
下一次循环i增加,看当前a[j]和a[i]是否满足a[i]-a[j]<=m,如果不满足,就让j增加,直到满足该条件。
循环跳出后,a[i]与a[j], a[j+1], …, a[i-1]数字的差值都满足小于等于m
也就是说,数对(a[j], a[i]),(a[j+1], a[i]),…,(a[i-1], a[i])都满足差值小于等于m。这样的以a[i]为较大数的差值小于等于m的数对有i-j个。
此时s增加i-j,可知s统计的就是整个序列中差值小于等于m的数对的个数。
如果序列中差值小于等于m的数对的个数大于等于k,则满足条件,否则不满足条件。

二分求的是满足条件的最小值,因此可以总结出f(a,k)求的是满足序列中差值小于等于m的数对的个数大于等于k的m的最小值。
或者可以将问题描述为:在序列a中找出不少于k个差值最大为m的数对,求数对差值m的最小值。

【试题答案及解析】

判断题
1.将第 24 行的 m 改为 m - 1,输出有可能不变,而剩下情况为少 1。()
答:T

    while (g < h) {int m = g + (h - g) / 2;if (f0(a, m, k)) {h = m;}else {g = m + 1;}}

如果恰好每次f0(a, m, k)都返回假,则每次都运行g=m+1,将h=m改为h=m-1不会影响程序运行,因为没有运行到这一句,因此输出不变。
对于其他情况,运行到h = m-1,由于此时m是满足条件(使f0(a, m, k)返回值为真)的值,而且m=h+1,所以h+1就是满足条件的值。
如果跳出时满足g等于h,输出g,比满足条件的正确结果h+1少1。
如果跳出时满足h+1等于g,输出g,与满足条件的正确结果h+1相等。
综上,该题叙述正确。

2.将第 22 行的 g + (h - g) / 2 改为 (h + g) >> 1,输出不变。()
答:T
(h + g) >> 1数值上就是(h+g)/2
g+(h - g)/2数值上也等于(h+g)/2
之所以写成g+(h - g)/2,是因为如果这样写,当h与g都接近int可以表示的最大数值时,表达式h+g的值仍然不会超过int可以表示的数值范围。
该问题序列a中的数值都不超过 1 0 8 10^8 108,相加后不会超过int的数值范围 2.1 ∗ 1 0 9 2.1*10^9 2.1109。所以这两种写法等价。
3.当输入为 5 7 2 -4 5 1 -3,输出为 5。()
答:T
n是5,k是7,数值有2 -4 5 1 3我们可以检查一下,当数对差值不超过5的情况下,能否找到不少于7个数对。
先排序:
-4 1 2 3 5
枚举所有数对,求差值
1-(-4)=5
2-(-4)=6
3-(-4)=7
5-(-4)=9
2-1=1
3-1=2
5-1=4
3-2=1
5-2=1
5-3=2
差值不超过5的数对有7个,满足大于等于k。如果差值更小为4,则差值不超过4的数对有6个,不满足大于等于k。因此差值最小为5,该题正确。
单选题
4.设 a 数组中最大值减最小值加 1 为 A,则 f 函数的时间复杂度为()。
A. O ( n log ⁡ A ) O(n \log A) O(nlogA)
B. O ( n 2 log ⁡ A ) O(n^2 \log A) O(n2logA)
C. O ( n log ⁡ ( n A ) ) O(n \log (nA)) O(nlog(nA))
D. O ( n log ⁡ n ) O(n \log n) O(nlogn)

答:C
f函数中首先对序列a进行了快速排序,序列a有n个元素,排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
而后进行二分,二分的的范围(也就是起始时上界减下界)为h-g,h为a中最大值减最小值,该题说a中最大值减(最小值加1)为A,所以A为h-1(另一种理解可以理解为A=h+1,但都不影响结果),该二分查找的比较次数为 O ( l o g ( h − g ) ) O(log(h-g)) O(log(hg))约为 O ( l o g A ) O(logA) O(logA)。每次比较调用了f0函数,f0函数中遍历了序列a,其时间复杂度为 O ( n ) O(n) O(n),所以整个二分过程的时间复杂度为 O ( n l o g A ) O(nlogA) O(nlogA)
整个f函数的时间复杂度为 O ( n l o g n + n l o g A ) = O ( n ( l o g n + l o g A ) ) = O ( n l o g ( n A ) ) O(nlogn+nlogA)=O(n(logn+logA))=O(nlog(nA)) O(nlogn+nlogA)=O(n(logn+logA))=O(nlog(nA))

5.将第 10 行中的 > 替换为 >=,那么原输出与现输出的大小关系为()。
A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对.

答:B
a[i] - a[j] > m变为a[i] - a[j] >= m,那么当while循环跳出时满足a[i]-a[j]<m
原题是要在序列a中找出不少于k个差值小于等于m的数对,求m的最小值。
假设对于该问题,输入n、k,得到的结果是m1,其中有k1(满足k1>=k)个数对差值小于等于m1。
现在变为:在序列a中找出不少于k个差值小于m的数对,求m的最小值。
如果还是输入n、k,得到的结果是m2。
由于在整个序列中差值小于等于m1的数对有k1个。
记差值小于m1的数对有k2个,由于小于m相较于小于等于m是更苛刻的条件,那么选出的数对可能更少,那么一定有k2<=k1。
如果k2>=k,那么对于当前问题,输入n、k,得到结果m2等于m1。
如果k2<k,那么为例增加差值小于m的数对,需要增加m,得到结果m2大于m1。
所以原输出m1相比现在的输出m2满足m1<=m2。即m1小于等于m2,不一定小于就是说有可能等于。选B。

6.当输入为 5 8 2 -5 3 8 -12,输出为()。
A. 13
B. 14
C. 8
D. 15

答:B
n是5,k是8,数值有2 -5 3 8 -12
先排序:
-12 -5 2 3 8
枚举所有数对,求差值
-5-(-12)=7
2-(-12)=14
3-(-12)=15
8-(-12)=20
2-(-5)=7
3-(-5)=8
8-(-5)=13
3-2=1
8-2=6
8-3=5
找出差值最小的8个数对,其中差值最大为14。
因此在该序列中找出不少于8个差值小于等于m的数对,m的最小值为14。
如果差值最大值m小于14,则无法找到8个数对。
选B

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com