分数: 300 分
问题陈述
高桥要组织一场国际象棋淘汰赛。 N 参加本次比赛的选手,每位编号从 1 to N。每个玩家 i 有评级 S_i,并且所有玩家都有不同的评级。
在锦标赛中,比赛会重复进行,直到仅 1 玩家依然存在。在每场比赛中, 2 尚未被淘汰的玩家被选择进行一对一的比赛。评分较高的玩家总是获胜,而失败的玩家则被淘汰。因此,总共 N - 1 比赛在整个锦标赛期间举行。
高桥作为组织者,可以自由决定哪一个 2 选手参加每场比赛。由于高桥提前知道所有选手的评分,并且可以完美预测每场比赛的结果,因此他可以在比赛开始前优化规划所有比赛配对。
高桥有一位他支持的球员:球员 K。高桥希望以最佳方式安排比赛配对,以最大限度地增加玩家的比赛次数 K 获胜。玩家 K 如果与评分更高的玩家比赛,就会输掉并被淘汰,之后获胜次数不再增加。
确定玩家的最大匹配数 K 可以获胜。
约束
- 2 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq S_i \leq 10^9
- 全部 S_i 是不同的
- 所有输入均为整数
输入
N K S_1 S_2 \ldots S_N
- 第一行包含 N,玩家数量,以及 K,高桥支持的玩家号码,以空格分隔。
- 第二行包含评级 每个玩家的 S_1, S_2, \ldots, S_N ,以空格分隔。
输出
一行输出玩家的最大匹配数 K 可以获胜。
示例输入 1
4 3 5 1 3 2
示例输出 1
2
示例输入 2
5 2 3 10 7 1 5
示例输出 2
4
示例输入 3
10 5 20 50 10 5 30 80 15 25 40 60
示例输出 3
5