java数据结构73:牛的选举

「爱情、让人受尽委屈。」 2023-02-20 06:22 46阅读 0赞

## 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

样例输出

实现代码如下：

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;
            }
        }
    }