题意

有n个任务，m个处理任务的队列。任务处理时间为a[1],...,a[n]。按顺序从1-n处理任务。问有多少对满足第i个任务完成时间严格大于第j个任务完成的时间。

题解

关键词

优先队列
树状数组

做法一

分为两步，第一步模拟求出结束的顺序，即得到一个数组b，b[i]表示第i号是第b[i]个办理完成的。这部分可模拟完成。
然后遍历，得到b[i]>b[j]的数量。这部分也是。
总复杂度，预计通过30%。

做法二

考虑加速做法一的两个部分。
模拟部分可以使用优先队列进行加速。的复杂度得到数组b。
求解，b[i]>b[j]的数量可以通过树状数组（或归并排序求逆序对的方法）加速。复杂度也是。
总复杂度，预计通过100%。

代码

#include <bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define ull unsigned ll
using namespace std;
const int maxn = 100100;
struct node {
    int id;
    ll t;
    bool operator < (const node & a) const {
        return a.t < t || (a.t == t && a.id < id);
    }
};
int f[maxn],ed[maxn];

class Solution {
public:
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
    int lowbit(int x) {return x&-x;}
    void upd(int i, int k, int n) {
        for (;i<=n;i+=lowbit(i)) f[i]+=k;
    }
    int ask(int i, int n) {
        int res=0;
        for (;i>0;i-=lowbit(i)) res += f[i];
        return res;
    }
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        priority_queue<node>q;
        int left = m, idx = 0;
        ll st = 0, ans = 0;
        for (int i=1;i<=n;i++) {
            if (left == 0) {
                node x = q.top(); q.pop();
                ed[x.id] = ++idx;
                upd(x.id,-1,n);
                ans += ask(x.id,n);
                st = x.t;
            } else left--;
            q.push((node){i, st+a[i-1]});
            upd(i,1,n);
        }
        while (!q.empty()) {
            node x = q.top(); q.pop();
            ed[x.id] = ++idx;
            upd(x.id,-1,n);
            ans += ask(x.id,n);
        }
        return ans;
    }
};