73:牛的选举
总时间限制:
1000ms
内存限制:
65536kB
描述
现在有N（1<=n<=50000）头牛在选举它们的总统，选举包括两轮：第一轮投票选举出票数最多的k（1<=k<=n）头牛进入第二轮；第二轮对k头牛重新投票，票数最多的牛当选为总统。< p="">
现在给出每头牛i在第一轮期望获得的票数Ai（1<=Ai<=1,000,000,000），以及在第二轮中（假设它进入第二轮）期望获得的票数Bi（1<=Bi<=1,000,000,000），请你预测一下哪头牛将当选总统。幸运的是，每轮投票都不会出现票数相同的情况。
<=n<=50000）头牛在选举它们的总统，选举包括两轮：第一轮投票选举出票数最多的k（1<=k<=n）头牛进入第二轮；第二轮对k头牛重新投票，票数最多的牛当选为总统。<>
输入
第1行：N和K
第2至N+1行：第i+1行包括两个数字：Ai和Bi
输出
当选总统的牛的编号（牛的编号从1开始）
样例输入
5 3
3 10
9 2
5 6
8 4
6 5
样例输出
5
实现代码如下：
import java.util.*; /** * @author baikunlong * @date 2020/6/23 12:10 */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); LinkedList<Cow> cows = new LinkedList<>(); for (int i = 0; i < n; i++) { cows.add(new Cow(scanner.nextInt(),scanner.nextInt(),i+1)); } cows.sort(Comparator.comparingInt(o->(o.first))); Collections.reverse(cows); while (cows.size()>k){ cows.removeLast(); } cows.sort(Comparator.comparingInt(o->(o.second))); Collections.reverse(cows); System.out.println(cows.get(0).index+""); } static class Cow{ int first; int second; int index; public Cow(int first, int second, int index) { this.first = first; this.second = second; this.index = index; } } }
