#8868. How Much Does Daytona Cost?
How Much Does Daytona Cost?
How Much Does Daytona Cost? / Daytona 价格多少?
版权信息: CF
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
Daytona 价格多少? | 2 sec | 1024 MB | 300 points |
题目描述
我们定义某个整数在一个子段上是 最常见的,如果它在该子段中的出现次数大于任何其他整数的出现次数。数组 a 的子段是数组中一段连续的元素。
给定一个大小为 n 的数组 a,以及一个整数 k,请判断是否存在一个非空子段,使得 k 是该子段中最常见的元素。
输入格式
输入包含多个测试用例。
- 第一行包含一个整数 t ( ),表示测试用例的数量。
- 每个测试用例包含两行:
- 第一行包含两个整数 n 和 k ( , ),分别表示数组的大小以及需要成为最常见元素的整数。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n ( ),表示数组的元素。
输出格式
对于每个测试用例,输出 "YES"
如果存在一个子段使得 k 是该子段中最常见的元素,否则输出 "NO"
。
你可以使用任意大小写输出(例如 "yEs"
, "yes"
, "Yes"
, "YES"
都被视为正确答案)。
输入输出示例
输入示例 1
7
5 4
1 4 3 4 1
4 1
2 3 4 4
5 6
43 5 60 4 2
2 5
1 5
4 1
5 3 3 1
1 3
3
5 3
3 4 1 5 5
输出示例 1
YES
NO
NO
YES
YES
YES
YES
题目分析
- 目标
- 判断是否存在一个子段,使得整数 k 在该子段中出现次数最多。
- 思路
- 直接判断 k 是否出现:如果 k 在数组中至少出现一次,就有可能构造一个子段使得它是最常见的元素。
- 检查 k 的分布情况:如果 k 至少出现两次(不一定连续),那么一定可以构造一个长度至少为 2 的子段,使得 k 是最常见的元素。
- 特例处理:如果数组长度为 1,那么只有当 a[0] == k 时答案为
"YES"
,否则为"NO"
。
- 优化策略
- 由于 n ≤ 100,可以使用 O(n²) 的暴力方式枚举所有子段并统计出现频率,但更简单的方法是只需检查 k 是否至少出现两次即可。
时间复杂度分析
操作 | 复杂度 |
---|---|
遍历数组查找k | O(n) |
处理t组测试用例 | O(t n) |
总复杂度 |
解题思路总结
- 读取输入数据,解析 n 和 k。
- 检查数组中 k 的出现次数:
- k 至少出现两次,直接输出
"YES"
。 - k 仅出现一次,可能需要额外判断是否能成为最常见元素。
- k 不出现,直接输出
"NO"
。
- k 至少出现两次,直接输出
- 优化思路:只需要扫描数组一次即可完成判断,时间复杂度为 **O(n)**。
解法基于 统计和贪心策略,通过简单扫描数组就能快速判断答案。