题解 | #排队#

题目：
银行有m个服务窗口，假设当前有n个人等待办理业务，那么这n个人会被顺序分配一个从1到n的号码。
第i号办理业务的时间都为,一个窗口一次只能办理一个人的业务，上一个人的业务办理完才能办理下一个人的业务，有多少对(i,j)，满足，且第i号办理业务完成的时间严格大于第j号办理业务完成的时间。
方法一：优先级队列+暴力
每次先办理完业务的窗口先空出来，因此采用优先级队列存储每个人办理业务的总时间，首先让开始时间为0进队，然后，对于遍历n个人，每次将第i个人的业务开始时间出队（空闲窗口），记录第i个人的业务办理总时间在ans数组中，并将总时间入队，直到所有人的业务办理时间都记录在ans数组中，暴力枚举数组中每个元素为i，累计ans[i]>ans[j]的个数

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长整型
     */
    public long getNumValidPairs (int n, int m, int[] a) {
        // write code here
        PriorityQueue<Long>q=new PriorityQueue<>();
        long[]ans=new long[n];
        for(int i=0;i<m;i++)q.add((long)0);//当前窗口的开始时间入队
        for(int i=0;i<n;i++){
            long time=q.peek();
            q.poll();//窗口空闲出队
            ans[i]=time+a[i];//记录总的时间=开始时间+持续时间
            q.add(ans[i]);//总的时间入队
        }
        long res=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(ans[i]>ans[j])res++;
            }
        }
        return res;
    }
}

复杂度：
时间复杂度： ,记录数组外层循环n次，优先级队列每次出队的时间复杂度为 ,再加上寻找逆序对个数双层循环的时间复杂度为 ,暴力解***超时
空间复杂度：,优先级队列的大小不超过m,ans数组大小不超过n
方法二：归并排序+优先级队列
由于直接暴力求解逆序对的时间复杂度过高会导致超时，因此我们可以采用归并排序来计算逆序对的个数
具体做法为：

• 左指针定位在数组的最左边，右指针定位到数组的最右边，不断找到数组的中点，从中点处分割，直到左右指针相遇，递归终止

• 将分割出来的每一个部分排序，也就是进入merge_sort函数,因为每一轮排序都是基于上一轮左右数组已排序好的情况下再排序，因此排序完毕后记得将已经排序好的temp部分相应拷贝到a数组部分

• 排序部分是从中点处分割数组为两部分，逐轮比较两部分的元素，将较小值放入辅助数组中，最后如果两部分中有剩余部分元素，则将剩余部分直接拷贝到中接下来的位置

• 因为每一轮排序都是基于上一轮左右数组已排序好的情况下再排序，因此每一轮排序中只要出现a[i]>a[j]则a[i]到a[mid]部分都大于a[j]，这一轮逆序对个数则等于mid-i+1,累加每一轮逆序对个数则得到整个数组的逆序对个数

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长整型
     */

    PriorityQueue<Long>q=new PriorityQueue<>();
    public long getNumValidPairs (int n, int m, int[] a) {
        // write code here
        long[]temp=new long[n];
        long[]ans=new long[n];
        for(int i=0;i<m;i++)q.add((long)0);//入队窗口开始时间
        for(int i=0;i<n;i++){
            long time=q.poll();//出队最短开始时间
            ans[i]=time+a[i];//总时间等于开始时间+持续时间
            q.add(ans[i]);
        }
        return merge_sort(0,n-1,ans,temp);
    }
    long merge_sort(int l,int r,long[]a,long[]temp){
        if(l>=r)return 0;//递归结束条件
        int mid=(l+r)>>1;
        long res=merge_sort(l,mid,a,temp)+merge_sort(mid+1,r,a,temp);
        int cnt=0,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(a[i]<=a[j])temp[cnt++]=a[i++];
            else{
                temp[cnt++]=a[j++];
                res+=mid-i+1;//a[i]到mid这段在之前已经排序好，则a[i]>a[j]时，a[i]到mid这段都比a[j]大
            }
        }
        while(i<=mid)temp[cnt++]=a[i++];
        while(j<=r)temp[cnt++]=a[j++];
        for(i=l,j=0;i<=r;i++,j++){
            a[i]=temp[j];//把排序好的元素复制回原数组，为下次寻找逆序对做准备
        }
        return res;
    }
}

复杂度：
时间复杂度： ,因为记录数组外层循环n次，优先级队列每次出队的时间复杂度为 ，归并排序时间复杂度为 ,
空间复杂度：,优先级队列的大小不超过m,ans和temp数组大小不超过n,