How Much Does Daytona Cost? / Daytona 价格多少？

版权信息： CF

任务总览

题目描述

我们定义某个整数在一个子段上是 ​最常见的​，如果它在该子段中的出现次数大于任何其他整数的出现次数。数组 a 的子段是数组中一段连续的元素。

给定一个大小为 n 的数组 ​a​，以及一个整数 ​k​，请判断是否存在一个非空子段，使得 k 是该子段中最常见的元素。

输入格式

输入包含多个测试用例。

• 第一行包含一个整数 t ( $1 \leq t \leq 1000$ )，表示测试用例的数量。
• 每个测试用例包含两行：
  • 第一行包含两个整数 n 和 k ( $1 \leq n \leq 100$ , $1 \leq k \leq 100$ )，分别表示数组的大小以及需要成为最常见元素的整数。
  • 第二行包含 n 个整数 a_1, a_2, ..., a_n ( $1 \leq a\_i \leq 100$ )，表示数组的元素。

输出格式

对于每个测试用例，输出 "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

题目分析

1. 目标
   • 判断是否存在一个子段，使得整数 k 在该子段中出现次数最多。
2. 思路
   • ​直接判断 k 是否出现​：如果 k 在数组中至少出现一次，就有可能构造一个子段使得它是最常见的元素。
   • ​检查 k 的分布情况​：如果 k 至少出现两次（不一定连续），那么一定可以构造一个长度至少为 2 的子段，使得 k 是最常见的元素。
   • ​特例处理​：如果数组长度为 1，那么只有当 a[0] == k 时答案为 "YES"，否则为 "NO"。
3. 优化策略
   • 由于 ​n ≤ 100​，可以使用 O(n²) 的暴力方式枚举所有子段并统计出现频率，但更简单的方法是只需检查 k 是否至少出现两次即可。

时间复杂度分析

解题思路总结

1. 读取输入数据，解析 n 和 ​k​。
2. 检查数组中 k 的出现次数：
   • k 至少出现两次，直接输出 "YES"。
   • k 仅出现一次，可能需要额外判断是否能成为最常见元素。
   • k 不出现，直接输出 "NO"。
3. ​优化思路​：只需要扫描数组一次即可完成判断，时间复杂度为 ​**O(n)**​。

解法基于 ​统计和贪心策略​，通过简单扫描数组就能快速判断答案。