题解 | #排队#

排队

http://www.nowcoder.com/practice/77fa1b6e4ca34fcfb2de7284f4d0f937

题意：

有 $n$ 个人，第 $i$ 个人办理事务需要 $a_i$ 时间，刚开始（时间点为 $0$ ）有 $m$ 个空闲窗口，现在按照第 $1\sim n$ 个人的顺序办理事务，当某个时刻发现有空闲窗口后，第 $i$ 个人会到那个空闲窗口办理事务

现在设第 $i$ 个人办理事务的截止时间为 $t_i$ ，求数组 $t$ 的逆序对个数

解法一（优先队列+暴力枚举求逆序对，不可AC）

我们设第 $i$ 个窗口已经花费的时间为 $c_i$ ，显然对于第 $i$ 个人，会到 $c_i$ 最小的那个窗口进行办理事务

由此我们可以维护一个优先队列（小根堆）

1. 初始化放 $m$ 个0到优先队列中

2. 对于第 $i$ 个弹出堆顶元素，设为 $x$ ，则 $t_i=x+a_i$

3. 将 $x+a_i$ 放入队列，代表对应的窗口花费时间增加 $a_i$

然后我们可以用双重循环来枚举所有数对，并且求出逆序对个数

代码：

class Solution {
public:
    long long t[100001];
    long long ans;
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        memset(t,0,sizeof t);//多测清空
        ans=0;//多测清空
        priority_queue<long long,vector<long long>,greater<long long> > pq;
        for(int i=1;i<=m;i++){
            pq.push(0);
        }
        for(int i=1;i<=n;i++){
            long long x=pq.top();
            pq.pop();
            t[i]=x+a[i-1];//求出第i个人的截至时间
            pq.push(t[i]);
        }
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(t[i]>t[j])ans++;//计算逆序对个数
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^2)$ ，维护优先队列的复杂度是 $O((n+m)logm)$ 的，双重循环计算逆序对的复杂度是 $O(n^2)$ ，故总的时间复杂度为 $O(n^2)$

空间复杂度： $O(n+m)$ ， $a,t$ 数组的空间都是 $O(n)$ 级别的，优先队列的空间是 $O(m)$ 级别的，故总的空间复杂度为 $O(n+m)$

解法二（优先队列+归并排序求解逆序对）

对于解法一中的逆序对问题，我们可以采用归并排序法来做

假设我们现在需要求解 $t[l,r]$ 范围内逆序对的个数

我们可以把 $t[l,r]$ 分割为 $t[l,mid]$ 和 $t[mid+1,r]$ 两部分

根据归并排序，我们知道数组 $t[l,mid]$ 和 $t[mid+1,r]$ 都是各自有序的（这边是从小到大排序）

我们记 $t[l,mid]=L[i]$ ， $t[mid+1,r]=R[j]$

当我们在归并的过程中发现 $L[i]>R[j]$ 时，例如下图所示：

因为数组 $L,R$ 都是按照升序排列的，若 $L[i]>R[j]$ ，则 $L[i]$ 后面所有的数字都一定大于 $R[j]$ ，由此我们就可以计算贡献了

代码：

class Solution {
public:
    long long t[100001];//第i个人完成的截止时间
    long long ans;//答案
    long long tmp[100001];//归并排序临时数组
    void merge_sort(int l,int r){
        if(l==r)return;//递归边界
        int mid=(l+r)>>1;
        merge_sort(l,mid);//左半边
        merge_sort(mid+1,r);//右半边
        int k=0;//记录当前归并了多少个元素
        int i=l,j=mid+1;//i是左半边指针，j是右半边指针
        while(i<=mid&&j<=r){
            if(t[i]<=t[j]){
                tmp[++k]=t[i++];
            }else{
                ans+=mid-i+1;//计算贡献
                tmp[++k]=t[j++];
            }
        }
        while(i<=mid){
            tmp[++k]=t[i++];
        }
        while(j<=r){
            tmp[++k]=t[j++];
        }
        for(int i=l;i<=r;i++){
            t[i]=tmp[i-l+1];//放回原数组
        }
    }
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        memset(t,0,sizeof t);
        ans=0;
        priority_queue<long long,vector<long long>,greater<long long> > pq;
        for(int i=1;i<=m;i++){
            pq.push(0);
        }
        for(int i=1;i<=n;i++){
            long long x=pq.top();
            pq.pop();
            t[i]=x+a[i-1];
            pq.push(t[i]);
        }
        merge_sort(1,n);//归并排序
        return ans;
    }
};