2022年CSP-X复赛真题及题解（T4：摧毁）

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输入 14 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输出 14 4 2 2说明/提示对于30 % 30\%30%的数据T 1 , 1 ≤ n ≤ 10 1 ≤ x i ≤ 10 1 ≤ c ≤ 10 T 1,1 \le n \le 101 \le x_i \le 101 \le c \le 10T1,1≤n≤101≤xi​≤101≤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 10001 \le c \le 1001≤n≤1031≤xi​≤10001≤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^61 \le c \le 1001≤T≤10,1≤n≤106,1≤xi​≤1061≤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可行。代码实现#includebits/stdc.husingnamespacestd;constintMAXV1000005;// 轨道编号最大值intcnt[MAXV];// 计数数组记录每个轨道的卫星数vectorintused;// 记录出现过非零的轨道编号intmain(){intT;// 测试组数scanf(%d,T);while(T--){intn,c;// 卫星总数脉冲武器代价scanf(%d %d,n,c);for(inti0;in;i){// 使用 i 而非 iintx;scanf(%d,x);if(cnt[x]0)used.push_back(x);// 首次出现记录轨道cnt[x];// 计数加一}longlongans0;// 答案可能较大用 long longfor(inti0;iused.size();i){// 遍历所有出现过的轨道intkused[i];ansmin(cnt[k],c);// 每个轨道取 min(卫星数, c)}printf(%lld\n,ans);// 重置计数为下一组数据做准备for(inti0;iused.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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}