2022年CSP-X复赛真题及题解（T3：动物园）

2022年CSP-X复赛真题及题解（T3：动物园）

题目描述

某动物园里有n nn个场馆和m mm种动物（m ≤ n m \le nm≤n）。

n nn个场馆的编号分别用1 , 2 , 3 , ⋯ , n 1,2,3, \cdots , n1,2,3,⋯,n表示；m mm种动物的编号分别用1 , 2 , 3 , ⋯ , m 1,2,3, \cdots , m1,2,3,⋯,m表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。

这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号a aa和b bb（起止编号会打印到游客购买的门票上），代表游客只能参观动物园的第a aa个场馆至第b bb个场馆（包含a , b a,ba,b）里的动物，其他的场馆不能去。门票按一个场馆十元收费。

如果你购买的门票的起止场馆编号是3 33到8 88，那么你需要花60 6060元钱购买门票，只能观看3 , 4 , 5 , 6 , 7 , 8 3,4,5,6,7,83,4,5,6,7,8号场馆的动物。

小明希望看到动物园内所有种类的动物，同时小明是个非常节约的孩子，他希望花最少的钱买门票。 请你帮小明计算：他最少需要花费多少钱买门票才能看到所有种类的动物（同一种动物他可能不止看一个）。注意：小明只能买一张门票。

输入格式

第一行两个整数n , m n,mn,m，分别表示动物园内的场馆数量及动物种类数量。

第二行是x 1 , x 2 , ⋯ , x n x_1,x_2, \cdots ,x_nx1​,x2​,⋯,xn​，其中x i x_ixi​表示第i ii个场馆中的动物种类编号。

输出格式

一行一个整数p pp，表示小明的门票费用。

输入输出样例 1

输入 1

12 5 2 5 3 1 3 2 4 1 1 5 4 3

输出 1

60

说明/提示

对于30 % 30\%30%的数据，有 $ n \le 200 , m \le 20$。

对于60 % 60\%60%的数据，有n ≤ 1000 , m ≤ 1000 n \le 1000 , m \le 1000n≤1000,m≤1000。

对于100 % 100\%100%的数据，有1 ≤ n ≤ 10 6 , 1 ≤ x i ≤ m ≤ 2 × 10 3 1 \le n \le 10^6,1 \le x_i \le m \le 2 \times 10^31≤n≤106,1≤xi​≤m≤2×103。

思路分析

这道题的本质是：在长度为 n 的序列中，找到一个最短的连续子区间，使得该子区间包含所有 m 种动物（即包含 1…m 的所有数字）。最终门票费用 = 最短子区间长度 × 10。

解法：滑动窗口（双指针）

1. 窗口定义：用左指针l和右指针r表示当前考察的区间[l, r]。
2. 扩展右指针：每次将r右移一位，把新场馆的动物加入窗口。用一个计数数组c记录每种动物在当前窗口内出现的次数。如果某种动物的数量从 0 变为 1，说明窗口新覆盖了一种动物，将已覆盖种类数cov加 1。
3. 收缩左指针：当cov == m时，说明当前窗口已经包含所有动物种类。此时尝试移动左指针l来缩小窗口，同时更新最短长度len。每移出左边界的一个动物，将其计数减 1，如果减到 0，则cov减 1。重复此过程直到窗口不再包含所有种类。
4. 记录答案：每次cov == m时，窗口长度r-l+1就是一个可行解，取最小值。
5. 最终费用：最短长度len乘以 10 即为答案。

时间复杂度 O(n)，空间复杂度 O(m)，满足 n ≤ 1e6, m ≤ 2000 的限制。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;vector<int>x(n+1);// 场馆动物种类，下标1..nfor(inti=1;i<=n;i++){cin>>x[i];}vector<int>c(m+1,0);// 当前窗口内每种动物的数量intcov=0;// 当前窗口已包含的种类数intl=1;// 窗口左边界intlen=n+1;// 最短窗口长度，初始化为大于n的值for(intr=1;r<=n;r++){// 右指针向右扩展intt=x[r];// 当前右边界动物种类c[t]++;// 加入窗口if(c[t]==1){// 该动物第一次出现cov++;// 覆盖种类数增加}while(cov==m){// 窗口已包含所有种类，尝试收缩左边界intcur=r-l+1;// 当前窗口长度if(cur<len){len=cur;// 更新最短长度}intlt=x[l];// 左边界动物种类c[lt]--;// 移出窗口if(c[lt]==0){// 该动物在窗口中消失cov--;// 覆盖种类数减少}l++;// 左指针右移}}intp=len*10;// 门票费用 = 场馆数 × 10元cout<<p<<endl;return0;}

功能分析

• 输入处理：读取场馆数量 n、动物种类数 m，以及 n 个场馆内饲养的动物种类编号（保证编号在 1…m 之间）。
• 核心算法：使用滑动窗口技术，维护一个动态区间[l, r]，通过右指针扩展和左指针收缩，找到覆盖所有 m 种动物的最短连续子区间。
• 计数与判断：利用计数数组c记录窗口内每种动物的出现次数，并用变量cov记录当前覆盖的种类数，当cov == m时满足条件。
• 结果输出：将最短子区间长度乘以 10，输出最小门票费用（单位：元）。

算法效率：时间复杂度 O(n)，空间复杂度 O(m)。

2022年CSP-X复赛真题及题解（T3：动物园）

题目描述

某动物园里有n nn个场馆和m mm种动物（m ≤ n m \le nm≤n）。

n nn个场馆的编号分别用1 , 2 , 3 , ⋯ , n 1,2,3, \cdots , n1,2,3,⋯,n表示；m mm种动物的编号分别用1 , 2 , 3 , ⋯ , m 1,2,3, \cdots , m1,2,3,⋯,m表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。

这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号a aa和b bb（起止编号会打印到游客购买的门票上），代表游客只能参观动物园的第a aa个场馆至第b bb个场馆（包含a , b a,ba,b）里的动物，其他的场馆不能去。门票按一个场馆十元收费。

如果你购买的门票的起止场馆编号是3 33到8 88，那么你需要花60 6060元钱购买门票，只能观看3 , 4 , 5 , 6 , 7 , 8 3,4,5,6,7,83,4,5,6,7,8号场馆的动物。

小明希望看到动物园内所有种类的动物，同时小明是个非常节约的孩子，他希望花最少的钱买门票。 请你帮小明计算：他最少需要花费多少钱买门票才能看到所有种类的动物（同一种动物他可能不止看一个）。注意：小明只能买一张门票。

输入格式

第一行两个整数n , m n,mn,m，分别表示动物园内的场馆数量及动物种类数量。

第二行是x 1 , x 2 , ⋯ , x n x_1,x_2, \cdots ,x_nx1​,x2​,⋯,xn​，其中x i x_ixi​表示第i ii个场馆中的动物种类编号。

输出格式

一行一个整数p pp，表示小明的门票费用。

输入输出样例 1

输入 1

12 5 2 5 3 1 3 2 4 1 1 5 4 3

输出 1

60

说明/提示

对于30 % 30\%30%的数据，有 $ n \le 200 , m \le 20$。

对于60 % 60\%60%的数据，有n ≤ 1000 , m ≤ 1000 n \le 1000 , m \le 1000n≤1000,m≤1000。

对于100 % 100\%100%的数据，有1 ≤ n ≤ 10 6 , 1 ≤ x i ≤ m ≤ 2 × 10 3 1 \le n \le 10^6,1 \le x_i \le m \le 2 \times 10^31≤n≤106,1≤xi​≤m≤2×103。

思路分析

这道题的本质是：在长度为 n 的序列中，找到一个最短的连续子区间，使得该子区间包含所有 m 种动物（即包含 1…m 的所有数字）。最终门票费用 = 最短子区间长度 × 10。

解法：滑动窗口（双指针）

1. 窗口定义：用左指针l和右指针r表示当前考察的区间[l, r]。
2. 扩展右指针：每次将r右移一位，把新场馆的动物加入窗口。用一个计数数组c记录每种动物在当前窗口内出现的次数。如果某种动物的数量从 0 变为 1，说明窗口新覆盖了一种动物，将已覆盖种类数cov加 1。
3. 收缩左指针：当cov == m时，说明当前窗口已经包含所有动物种类。此时尝试移动左指针l来缩小窗口，同时更新最短长度len。每移出左边界的一个动物，将其计数减 1，如果减到 0，则cov减 1。重复此过程直到窗口不再包含所有种类。
4. 记录答案：每次cov == m时，窗口长度r-l+1就是一个可行解，取最小值。
5. 最终费用：最短长度len乘以 10 即为答案。

时间复杂度 O(n)，空间复杂度 O(m)，满足 n ≤ 1e6, m ≤ 2000 的限制。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cin>>n>>m;vector<int>x(n+1);// 场馆动物种类，下标1..nfor(inti=1;i<=n;i++){cin>>x[i];}vector<int>c(m+1,0);// 当前窗口内每种动物的数量intcov=0;// 当前窗口已包含的种类数intl=1;// 窗口左边界intlen=n+1;// 最短窗口长度，初始化为大于n的值for(intr=1;r<=n;r++){// 右指针向右扩展intt=x[r];// 当前右边界动物种类c[t]++;// 加入窗口if(c[t]==1){// 该动物第一次出现cov++;// 覆盖种类数增加}while(cov==m){// 窗口已包含所有种类，尝试收缩左边界intcur=r-l+1;// 当前窗口长度if(cur<len){len=cur;// 更新最短长度}intlt=x[l];// 左边界动物种类c[lt]--;// 移出窗口if(c[lt]==0){// 该动物在窗口中消失cov--;// 覆盖种类数减少}l++;// 左指针右移}}intp=len*10;// 门票费用 = 场馆数 × 10元cout<<p<<endl;return0;}

功能分析

• 输入处理：读取场馆数量 n、动物种类数 m，以及 n 个场馆内饲养的动物种类编号（保证编号在 1…m 之间）。
• 核心算法：使用滑动窗口技术，维护一个动态区间[l, r]，通过右指针扩展和左指针收缩，找到覆盖所有 m 种动物的最短连续子区间。
• 计数与判断：利用计数数组c记录窗口内每种动物的出现次数，并用变量cov记录当前覆盖的种类数，当cov == m时满足条件。
• 结果输出：将最短子区间长度乘以 10，输出最小门票费用（单位：元）。

算法效率：时间复杂度 O(n)，空间复杂度 O(m)。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

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

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

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

3、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 点击跳转

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

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

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

5、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 点击跳转

· 文末祝福 ·

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