#3575. [USACO13MAR] Breed Proximity B
[USACO13MAR] Breed Proximity B
P3085 [USACO13OPEN] Breed Proximity G
题目描述
农夫约翰的N头奶牛(1 ≤ N ≤ 50,000)排成一列,每头奶牛都有一个整数品种ID。
相同品种的奶牛如果站得太近可能会发生争执。具体来说,如果两头相同品种奶牛的位置差不超过K(1 ≤ K < N),则称它们为"拥挤对"。
请计算所有拥挤对中最大的品种ID。如果没有拥挤对存在,则输出-1。
输入格式
第一行:两个空格分隔的整数N和K
接下来N行:每行包含一头奶牛的品种ID(0 ≤ ID ≤ 1,000,000)
输出格式
一个整数,表示拥挤对中的最大品种ID,若无拥挤对则输出-1
输入输出样例
输入 #1
6 3
7
3
4
2
3
4
输出 #1
4
样例解释
6头奶牛的品种ID依次为:7、3、4、2、3、4
拥挤对有:
- 品种3的奶牛(位置2和5,差值为3)
- 品种4的奶牛(位置3和6,差值为3)
其中最大的品种ID是4