首页 > 试题广场 >

拉票

[编程题]拉票
  • 热度指数:324 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小明正在参加一次选举。这次选举一共有n个人参与投票,每个人都最多投1票且必须投1 票。每一个人都隶属于且仅隶属于一个阵营,第 a_i个人隶属的阵营编号为 。小明隶属的阵营编号为 x,所有隶属于该阵营的人(允许没有人属于该阵营的情况出现)都一定会投票给小明,其他阵营的人都不会主动投票给小明。小明自己不参与投票,这 n个人当中也不包含小明。 
在最终投票前,小明决定再游说 1个阵营投票给自己。如果小明游说成功,则隶属于被游说阵营的所有人都会投票给小明。小明会选择1个阵营进行游说,使得最后获得的总票数尽可能多。如果在小明游说前这n 个人已经全部隶属于小明所在的阵营,则小明不会展开游说。 
假设小明游说一定成功,则小明在最终投票中最多可以获得多少票?

输入描述:
输入第一行包含两个整数 n( 1 \leq n \leq 10^5)和 x(1 \leq x \leq n),分别表示参与投票的总人数和小明隶属的阵营编号。
输入第二行包含n个整数,其中第 i 个整数(1 \leq a_i \leq n) 表示了第 i 个人隶属的阵营编号。


输出描述:
输出一行,一个整数,表示小明在最终投票中最多可以获得的票数。
示例1

输入

6 2
1 2 2 2 3 3

输出

5

说明

小明隶属于编号为2的阵营,获得3票;小明选择游说编号为3的阵营,再获得2票,一共获得5票。

这道题你会答吗?花几分钟告诉大家答案吧!