题解 | #排队#

##################################################################################
########优先级队列，其中意义是指：每个位置在什么时候空闲 + 归并排序求逆序对 ###### import java.util.*;


public class Solution {
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型一维数组 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
    long count = 0;
    public long getNumValidPairs (int n, int m, int[] a) {
        // write code here
        PriorityQueue<Long>priority = new PriorityQueue<Long>();///最小堆
        //PriorityQueue<Integer>priority = new PriorityQueue<>(new Comparator(){
//             public int compare(Integer o1,Integer o2){
//                 return o2-o1;
//             }
//         });
        for(int i=0;i<m;i++){
            priority.add(0l);
        }
        long[]finished = new long[n];
        for(int i = 0;i < n;i++){
            long time = priority.peek();
            long fitime = time + a[i];
            finished[i] = fitime;
            priority.poll();
            priority.add(fitime);
        }
        //求逆序对
        long[]temp = new long[n];
        Merge(finished,0,n-1,temp);
        return count;
    }
    void Merge(long[]arr,int low,int high,long[]temp){
        if(low<high){
            int mid = low + (high-low)/2;
            Merge(arr,low,mid,temp);
            Merge(arr,mid+1,high,temp);
            MergeSort(arr,low,mid,high,temp);
        }
    }
    void MergeSort(long[]arr,int low,int mid,int high,long[]temp){
        int left1 = low;
        int left2 = mid+1;
        int k = 0;
        while(left1<=mid && left2<=high){
            if(arr[left1]>arr[left2])
            {
                count += mid-left1+1;
                temp[k++] = arr[left2++];
            }else{
                temp[k++] = arr[left1++];
            }
       }
        while(left1<=mid) temp[k++] = arr[left1++];
        while(left2<=high) temp[k++] = arr[left2++];
        for(int i=0;i<k;i++){
            arr[low+i] = temp[i];
        }
    }
}