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

排队

https://ac.nowcoder.com/acm/problem/207273

题目

银行有 个服务窗口,假设当前有 个人等待办理业务,那么这 个人会被顺序分配一个从 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;
    }
};
全部评论

相关推荐

码农索隆:想看offer细节
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-25 17:13
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务