← 返回题目列表

AtCoder · awc0013_c

C. 锦标赛的最佳配对

中文机器翻译题面 查看原题

分数: 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