【牛客编程巅峰赛S1第5场】排队

题目

银行有 个服务窗口，假设当前有 个人等待办理业务，那么这 个人会被顺序分配一个从 1 到 的号码。

等待办理业务的流程如下：
从第 1 号到第 号顺序的进行排队。
假设当前第 1 号到第 号都正在办理或已经办理完业务，且某个窗口 A 没有客人正在办理业务，那么第 号会马上到窗口 A 办理业务。
如果有多个这样的窗口，第 号会随意选择一个窗口。

在 0 时刻，有 个窗口都没有客人正在办理业务，而 个人正在等待办理业务。
假设第 号不管在哪个窗口办理业务，办理业务的时间都为 。

求：有多少对 ，满足 ，且第 号办理业务完成的时间严格大于第 号办理业务完成的时间。

解题思路

遍历 a，同时维护一个最小优先队列 pq，使用数组 t 记录每个人办理业务完成的时间。
队列 pq 表示当第 i 个人开始办理业务时，m 个窗口没有客人的时间。获取最早空闲的窗口，其时间为 pq.top()，那么第 i 个人到该窗口办理业务，其完成时间为 pq.top() + a[i]，记录到 t[i] 中，并更新队列。

现在，求数组 t 中有多少个逆序对，此即为题目所求。

使用归并排序求逆序对

归并排序包含这样三个步骤：

• 分解：待排序的区间为 ，令 ，我们把 分成 和
• 解决：使用归并排序递归地排序两个子序列
• 合并：把两个已经排好序的子序列 和 合并起来

在待排序序列长度为 1 的时候，递归开始回升，因为默认长度为 1 的序列是排好序的。

假设有两个已排序的序列 和 等待合并。
将 和 分别指向上述两个序列。当 比 小，但比 中的其他数大时， 贡献了 个逆序对。

例如，假设是 和 。
一开始用指针 指向 的头部， 指向 的头部。此时，，6 对逆序对总数的贡献为 0。
接着，，此时 12 小于 20，12 的贡献为 1。
接着，，此时 16 小于 20，16 的贡献为 1。
接着，，此时 24 小于 54，24 的贡献为 3。
总贡献为 0 + 1 + 1 + 3 = 5，即 5 对逆序对。

C++代码

class Solution {
    long long cnt;
    void merge(vector<long long>& t, int b, int mid, int e){
        if(b >= e)
            return;
        vector<long long> L(t.begin()+b, t.begin()+mid+1);
        vector<long long> R(t.begin()+mid+1, t.begin()+e+1);
        int i = 0;
        int j = 0;
        int k = b;
        while(i<L.size() && j<R.size()){
            if(L[i]<=R[j]){
                t[k] = L[i];
                cnt += j;
                ++i;
            }
            else{
                t[k] = R[j];;
                ++j;
            }
            ++k;
        }
        while(i<L.size()){
            cnt += j;
            t[k] = L[i];
            ++k;
            ++i;
        }
        while(j<R.size()){
            t[k] = R[j];
            ++k;
            ++j;
        }
    }
    void mergeSort(vector<long long>& t, int b, int e){
        if(b >= e)
            return;
        int mid = b + (e-b)/2;
        mergeSort(t, b, mid);
        mergeSort(t, mid+1, e);
        merge(t, b, mid, e);
    }
public:
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        // write code here
        vector<long long> tmp(m, 0);
        priority_queue<long long, vector<long long>, greater<long long> > pq(tmp.begin(), tmp.end());

        vector<long long> t(n);
        for(int i=0; i<n; ++i){
            long long tmp = pq.top() + a[i];
            t[i] = tmp;
            pq.pop();
            pq.push(tmp);
        }
        cnt = 0;
        mergeSort(t,0,n-1);
        return cnt;
    }
};