2022年CSP-X复赛真题及题解（T4：摧毁）
题目描述
坐地日行八万里，巡天遥看一千河。
2077 年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。
人类有两种不同的武器可以摧毁卫星，具体如下（其中P W \rm PWPW为新的能量单位）：
使用定点激光武器花费1 P W 1\ \rm{PW}1PW的代价摧毁任意轨道上指定的一个卫星。
使用脉冲轨道武器花费c P W c\ \rm{PW}cPW的代价把某一轨道上的所有卫星摧毁。
现在有n nn个旧卫星分布在不同的外轨道上，你的任务是摧毁这些旧卫星。给出这n nn个卫星的轨道编号，求将这些卫星全部摧毁的最小代价是多少？
输入格式
第一行一个正整数T TT，表示测试数据组数。
接下来对于每组测试数据（注意：每组测试数据有2 22行数据，以下共2 T 2T2T行数据）：
第一行两个正整数n nn和c cc表示需要摧毁的卫星数量和使用脉冲轨道武器的代价。
第二行 是x 1 , x 2 , x 3 , ⋯ , x n x_1,x_2,x_3,\cdots, x_nx1,x2,x3,⋯,xn，其中x i x_ixi表示第i ii个卫星的轨道编号。
输出格式
输出T TT行答案，对于每组测试数据，输出一行一个整数表示摧毁所有卫星的代价。
输入输出样例 1
输入 1
4 10 1 2 1 4 5 2 4 5 5 1 2 5 2 3 2 1 2 2 2 2 1 1 2 2 1 2输出 1
4 4 2 2说明/提示
对于30 % 30\%30%的数据，T = 1 , 1 ≤ n ≤ 10 ， 1 ≤ x i ≤ 10 ， 1 ≤ c ≤ 10 T = 1,1 \le n \le 10，1 \le x_i \le 10，1 \le c \le 10T=1,1≤n≤10，1≤xi≤10，1≤c≤10；
对于60 % 60\%60%的数据，1 ≤ n ≤ 10 3 ， 1 ≤ x i ≤ 1000 ， 1 ≤ c ≤ 100 1 \le n \le 10^3， 1 \le x_i \le 1000，1 \le c \le 1001≤n≤103，1≤xi≤1000，1≤c≤100；
对于100 % 100\%100%的数据，1 ≤ T ≤ 10 , 1 ≤ n ≤ 10 6 , 1 ≤ x i ≤ 10 6 ， 1 ≤ c ≤ 100 1 \le T \le 10,1 \le n \le 10^6, 1 \le x_i \le 10^6，1 \le c \le 1001≤T≤10,1≤n≤106,1≤xi≤106，1≤c≤100，且所有测试数据的n nn加起来不超过10 6 10^6106。
思路分析
问题要求摧毁所有卫星的最小代价。每个轨道上的卫星可以逐个摧毁（每个花费1 PW），也可以使用脉冲武器一次摧毁整个轨道（花费 c PW）。因此，对于每个轨道，若该轨道上有 k 颗卫星，则摧毁该轨道卫星的最优代价为 min(k, c)。总代价即为所有轨道的 min(k, c) 之和。
实现步骤：
- 读取测试组数 T。
- 对于每组测试数据：
- 读取 n 和 c。
- 统计每个轨道编号出现的次数（轨道编号范围 1~10^6，可用数组计数）。
- 使用一个数组
cnt记录每个轨道的卫星数，一个列表used记录出现过的轨道编号，避免遍历全部范围。 - 对每个输入的轨道编号
x，若cnt[x]==0则将其加入used，然后cnt[x]++。 - 遍历
used中的所有轨道，累加min(cnt[轨], c)到答案。 - 重置
used中轨道的计数为 0，并清空used列表，准备下一组数据。
- 输出每组答案。
复杂度：O(n + 不同轨道数)，不同轨道数 ≤ n，总和 n ≤ 10^6，可行。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintMAXV=1000005;// 轨道编号最大值intcnt[MAXV];// 计数数组，记录每个轨道的卫星数vector<int>used;// 记录出现过（非零）的轨道编号intmain(){intT;// 测试组数scanf("%d",&T);while(T--){intn,c;// 卫星总数，脉冲武器代价scanf("%d %d",&n,&c);for(inti=0;i<n;i++){// 使用 i++ 而非 ++iintx;scanf("%d",&x);if(cnt[x]==0)used.push_back(x);// 首次出现，记录轨道cnt[x]++;// 计数加一}longlongans=0;// 答案，可能较大，用 long longfor(inti=0;i<used.size();i++){// 遍历所有出现过的轨道intk=used[i];ans+=min(cnt[k],c);// 每个轨道取 min(卫星数, c)}printf("%lld\n",ans);// 重置计数，为下一组数据做准备for(inti=0;i<used.size();i++)cnt[used[i]]=0;used.clear();}return0;}功能分析
- 输入处理：使用
scanf快速读取整数，适合大规模输入。 - 统计频率：数组
cnt下标为轨道编号，值为该轨道的卫星数；used向量记录所有非零轨道，避免遍历整个数组范围。 - 代价计算：对每个轨道，取
min(cnt[轨], c)并累加到答案。 - 重置操作：每次处理完一组数据后，将
used中记录的轨道的cnt重置为 0，并清空used，确保下一组数据不受干扰。 - 输出：每行输出一个整数，表示该组测试数据的最小代价。
更多内容请关注专栏：信奥赛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;}
