牛客网真题2019-14-塔

面向对象编程：堆
java提供了优先级队列PriorityQueue，底层是堆实现的，建立每一个塔对象，用两个优先级队列包含所有塔，一个大根堆，一个小根堆。
然后就简单了，从大小根堆取出对象，执行对象的add,remove方法，然后把操作日志记录到arraylist中去。
该思路帮助回忆了一手堆和优先级队列用法，面向对象思想QAQ.ps:lambda表达式真优美。

import java.util.*;

class Tow {
    int id;
    int num;

    public Tow(int id, int num){
        this.id = id;
        this.num = num;
    }

    public void add(){
        num++;
    }

    public void remove(){
        num--;
    }
}

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Queue<Tow> minQ = new PriorityQueue<>(new Comparator<Tow>() {
            @Override public int compare(Tow o1, Tow o2){
                return Integer.compare(o1.num, o2.num);
            }
        });
        PriorityQueue<Tow> maxQ = new PriorityQueue<>(new Comparator<Tow>() {
            @Override public int compare(Tow o1, Tow o2){
                return Integer.compare(o2.num, o1.num);
            }
        });
        for(int i = 0; i < n; i++){
            Tow temp = new Tow(i + 1, sc.nextInt());
            //            System.out.println(temp.num);
            minQ.add(temp);
            maxQ.add(temp);
        }

        int m = 0;
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        for(int i = 1; i <= k; i++){
            if(minQ.peek().num < maxQ.peek().num){
                Tow max = maxQ.poll();
                Tow min = minQ.poll();
                max.remove();
                min.add();
                arr1.add(max.id);
                arr2.add(min.id);
                maxQ.add(max);
                minQ.add(min);
                m++;
            }else{
                break;
            }
        }
        System.out.println(maxQ.peek().num - minQ.peek().num + " " + m);
        for(int i = 0; i < arr1.size(); i++){
            System.out.println(arr1.get(i) + " " + arr2.get(i));

        }
    }
}