牛客编程巅峰赛S1第5场 - 青铜&白银 C.排队 (优先队列,归并排序)

题意:有\(m\)个窗口,\(n\)个人排队,每个人都有各自的办理时间,只有办理完成窗口才能空出来,后面的人开始办理,求有多少人比后面的人开始办理的早但完成的晚.
题解:我们可以用优先队列来模拟办理,用一个数组q来记录办理完成的时间,之后只要求q中逆序对的个数即可,既然求逆序对,那我们肯定用归并排序啦～

代码:

class Solution {

public:

    /**

     * 求解合法的(i,j)对的数量

     * @param n int整型 n个人

     * @param m int整型 m个窗口

     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间

     * @return long长整型

     */

    long long q[1000010];

    long long t[1000010];

    long long res;

    priority_queue<long long,vector<long long>,greater<long long>> h;

    long long merge_sort(long long q[],int l,int r){

    if(l==r) return 0;

    int mid=(l+r)>>1;

    res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);

    int i=l,j=mid+1;

    int cnt=0;

    while(i<=mid && j<=r){

        if(q[i]<=q[j]) t[++cnt]=q[i++];

        else{

            t[++cnt]=q[j++];

            res+=mid-i+1;

        }

    }

    while(i<=mid) t[++cnt]=q[i++];

    while(j<=r) t[++cnt]=q[j++];

    for(int i=l,j=1;i<=r;++i,++j) q[i]=t[j];

    return res;

    }

    long long getNumValidPairs(int n, int m, vector<int>& a) {

        for(int i=0;i<m;++i){

            h.push(0);

        }

        for(int i=0;i<n;++i){

            long long tmp=h.top()+a[i];

            q[i+1]=tmp;

            h.pop();

            h.push(tmp);

        }

        res=merge_sort(q,1,n);

        return res;

    }

};

巴特西

牛客编程巅峰赛S1第5场 - 青铜&白银 C.排队 (优先队列,归并排序)

最新文章

热门文章