#P9460. 「EZEC-14」众数 I

    ID: 8703 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>贪心洛谷原创O2优化前缀和洛谷月赛

「EZEC-14」众数 I

题目背景

pigstd 是一个可爱的男孩子。他在 NOI2022 中的众数一题定义了 10610^6std::deque 并没有 MLE。

题目描述

给定一个长度为 nn 的序列 aa,我们通过以下方式构造序列 bb

  • 初始时 b=ab=a
  • 依次对 bb 进行 kk 次操作,每次操作选择任意一个元素并将其修改为任意整数。

dXqwq 定义一个序列的众数为所有出现次数最大的数。例如 [1,1,4,5,1,4][1,1,4,5,1,4] 的众数为 11,而 [1,14,5,14,19,19,8,10][1,14,5,14,19,19,8,10] 的众数为 14,1914,19

你需要求出有多少整数可能成为 bb众数

输入格式

第一行输入两个整数 n,kn,k

第二行输入 nn 个整数 aia_i

输出格式

输出一个整数,代表可能成为众数的数的数量。

特别地,如果答案为正无穷,输出 pigstd

5 0
1 2 3 4 5
5
5 1
1 2 3 4 5
pigstd
5 1
1 1 2 2 3
3

提示

【样例解释】

对于第一组数据,最终 1,2,3,4,51,2,3,4,5 可能为区间众数。

对于第二组数据,将第一个数换成 6,7,8,9,6,7,8,9,\cdots 后它们均会成为区间众数,因此答案为正无穷。

对于第三组数据,1,2,31,2,3 可能成为区间众数。

【提示】

10610^6std::deque 在空间限制为 1024MB 时不一定会 MLE。

【数据范围】

本题采用捆绑测试。

  • Subtask 1(20 pts):n5n\leq 5
  • Subtask 2(20 pts):n103n\leq 10^3
  • Subtask 3(20 pts):k=0k=0
  • Subtask 4(20 pts):k=1k=1
  • Subtask 5(20 pts):无特殊限制。

对于 100%100\% 的数据,1n1061\leq n\leq 10^60kn0\leq k\leq n 1ain1\leq a_i\leq n