#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 ( 1t10001 \leq t \leq 1000 ),表示测试用例的数量。
  • 每个测试用例包含两行:
    • 第一行包含两个整数 nk ( 1n1001 \leq n \leq 100 , 1k1001 \leq k \leq 100 ),分别表示数组的大小以及需要成为最常见元素的整数。
    • 第二行包含 n 个整数 a_1, a_2, ..., a_n ( 1a_i1001 \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 是否至少出现两次即可。

时间复杂度分析

操作 复杂度
遍历数组查找k O(n)
处理t组测试用例 O(t n)
总复杂度

解题思路总结

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

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