题解 | #排队#

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());</long></long></long></int></long></long></long></long>

    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;
}

};