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

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

题目描述

坐地日行八万里，巡天遥看一千河。

2077 年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。

人类有两种不同的武器可以摧毁卫星，具体如下（其中

P

W

\\rm PW

PW 为新的能量单位）：

现在有

n

n

n 个旧卫星分布在不同的外轨道上，你的任务是摧毁这些旧卫星。给出这

n

n

n 个卫星的轨道编号，求将这些卫星全部摧毁的最小代价是多少？

输入格式

第一行一个正整数

T

T

T，表示测试数据组数。

接下来对于每组测试数据（注意：每组测试数据有

2

2

2 行数据，以下共

2

T

2T

2T 行数据）：

第一行两个正整数

n

n

n 和

c

c

c 表示需要摧毁的卫星数量和使用脉冲轨道武器的代价。

第二行 是

x

1

,

x

2

,

x

3

,

⋯
 

,

x

n

x_1,x_2,x_3,\\cdots, x_n

x1​,x2​,x3​,⋯,xn​，其中

x

i

x_i

xi​ 表示第

i

i

i 个卫星的轨道编号。

输出格式

输出

T

T

T 行答案，对于每组测试数据，输出一行一个整数表示摧毁所有卫星的代价。

输入输出样例 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 10

T=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 100

1≤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 100

1≤T≤10,1≤n≤106,1≤xi​≤106，1≤c≤100，且所有测试数据的

n

n

n 加起来不超过

10

6

10^6

106。

思路分析

问题要求摧毁所有卫星的最小代价。每个轨道上的卫星可以逐个摧毁（每个花费1 PW），也可以使用脉冲武器一次摧毁整个轨道（花费 c PW）。因此，对于每个轨道，若该轨道上有 k 颗卫星，则摧毁该轨道卫星的最优代价为 min(k, c)。总代价即为所有轨道的 min(k, c) 之和。

实现步骤：

复杂度：O(n + 不同轨道数)，不同轨道数 ≤ n，总和 n ≤ 10^6，可行。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1000005; // 轨道编号最大值
int cnt[MAXV];// 计数数组，记录每个轨道的卫星数
vector<int> used; // 记录出现过（非零）的轨道编号

int main() {
int T; // 测试组数
scanf("%d", &T);
while (T—) {
int n, c; // 卫星总数，脉冲武器代价
scanf("%d %d", &n, &c);
for (int i = 0; i < n; i++) { // 使用 i++ 而非 ++i
int x;
scanf("%d", &x);
if (cnt[x] == 0) used.push_back(x); // 首次出现，记录轨道
cnt[x]++; // 计数加一
}
long long ans = 0; // 答案，可能较大，用 long long
for (int i = 0; i < used.size(); i++) { // 遍历所有出现过的轨道
int k = used[i];
ans += min(cnt[k], c); // 每个轨道取 min(卫星数, c)
}
printf("%lld\\n", ans);
// 重置计数，为下一组数据做准备
for (int i = 0; i < used.size(); i++) cnt[used[i]] = 0;
used.clear();
}
return 0;
}

功能分析

• 输入处理：使用 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>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}