题意概述

  • m个窗口，n个人去办理业务
  • 如果窗口有空，人则办理业务，否则等待
  • 问所有人的业务完成时间所组成的序列中的逆序数

    方法一：归并求逆序数

    思路与具体做法

  • 首先根据题意应该先求每个客人的业务完成时间，具体做法是先在优先队列中压入空闲窗口个数个0，之后不断取队首元素出队，加上当前客人活动时间后，再加入队尾
  • 接着归并排序求逆序数
  • 归并排序步骤
    • 划分：将待排序区间，按照，划分成两段，。
    • 合并：对，使用递归排序，并合并成新的有序序列。
  • 如归并段>归并段，按从小到大排列，先加入temp，加入temp数组后会在后，这样就是一个逆序对。因为归并段内是有序的，易知以后的所有元素也都比大，加入temp数组后也都在后，所以本次统计逆序对个数为及以后的所有数。 
class Solution {
public:
    priority_queue<long long,vector<long long>,greater<long long> >q;//按数字从小到大排列 
    long long merge_sort(int l,int r,vector<long long>&a,vector<long long>&temp){
        if(l>=r)return 0;//递归边界 
        int mid=(l+r)>>1;//划分 
        long long ans=merge_sort(l,mid,a,temp)+merge_sort(mid+1,r,a,temp);

        int cn=0,i=l,j=mid+1;//合并 
        while(i<=mid&&j<=r){//两路归并排序并用temp数组暂存 
            if(a[i]<=a[j])temp[cn++]=a[i++];
            else{
                temp[cn++]=a[j++];
                ans+=mid-i+1;//统计逆序对，此时a[i]>a[j],即a[i]~a[mid]都排在a[j]后面,i~mid排好的数和j都能构成逆序对,数量为mid-i+1 
            }
        }    
        while(i<=mid)temp[cn++]=a[i++];//所分两路分别有序，如有剩余，直接加到temp数组后面 
        while(j<=r)temp[cn++]=a[j++];

        for(int i=l,j=0;i<=r;i++,j++){//temp数组的写回 
            a[i]=temp[j];
        }
        return ans;
    } 
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        for(int i=0;i<m;i++){
            q.push(0);
        }
        vector<long long>s(a.size(),0);//提高精度，因为在队列中不断加会超过int数范围
        vector<long long>temp(a.size(),0);
        for(int i=0;i<n;i++){
            long long t=q.top();q.pop();//每次取队首最小值出队
            s[i]=t+a[i];
            q.push(s[i]);//更新后再入队
        } 
        return merge_sort(0,n-1,s,temp);
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，n为序列元素个数,归并排序的时间复杂度，递归树高（即归并趟数），每层共计n个数组元素，所以总的时间复杂度。
空间复杂度：，只用到了长度为n的辅助数组temp。

方法二：树状数组求逆序数

相关知识

树状数组相关操作

  • 定义数组 
int c[maxn];//树状数组 
int lowbit(x){//将二进制最后一位1置0 
    return x&-x;
}
  • 单点更新，将第x个整数加上v
    • 从当前结点不断向父结点走的“爬树”操作，直到树状数组的容量MAXN，中途不断跟新元素值
    • 时间复杂度： 
void update(int x,int v){
    for(int i=x;i<=N;i++){
        c[i]+=v;
    }
}
  • 区间查询，返回前x整数之和
    • 如果要求前11项和，(11)10=(1011)2，不断去掉二进制最右边一个1
    • 可以分别查询((1010)2,(1011)2]，((1000)2,(1010)2]，((0000)2,(1000)2]，的和再相加即可
    • 时间复杂度： 
int getSum(int x){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i)){
        sum+=c[i];
    }
}
  • 若想区间查询[a,b]，即可
  • 求序列元素第k大
    • 如果用数组记录每个元素出现的次数，那么序列第大就是在求最小的，使成立
    • 即寻找第一个满足条件的i
    • 具体做法是令,，然后在范围内进行二分
      • 说明所求位置不超过,令
      • 说明所求位置大于,令
    • 直到不成立为止
    • 时间复杂度： ,二分，求和各有 
int findKthElement(int k){
    int l=1,r=MAXN,mid;//初始区间为[1,MAXN] 
    while(l<r){
        mid=(l+r)/2;
        if(getSum(mid)>=k)r=mid;
        else l=mid+1;
    } 
    return l;
}
  • 区间修改，将前x个整数都加上v 
void update(int x,int v){
    for(int i=x;i>0;i-=lowbit(i)){
        c[i]+=v;
    }
}
  • 单点更新，返回第x整数的值 
int getSum(int x){
    int sum=0;
    for(int i=x;i<maxn;i+=lowbit(i)){
        sum+=c[i];
    }
    return sum;
}
  • 定义二维数组 
int c[maxn][maxn];//二维树状数组
  • 二维update函数，位置为(x,y)的整数加上v 
void update(int x,int y,int v){
    for(int i=x;i<maxn;i+=lowbit(i)){
        for(int j=y;j<maxn;j+=lowbit(i)){
            c[i][j]+=v;
        }
    }
}
  • 二维getSum函数返回(1,1)到(x,y)的子矩阵中元素之和 
int getSum(int x,int y){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i)){
        int sum=0;
        for(int j=y;j>0;j-=lowbit(i)){
            sum+=c[i][j];
        }
    }
}
  • 若想求~这个子矩阵的元素之和，只需要计算
  • 更高维的情况只需要吧for循环改为相应的重数即可

离散化

  • 对于序列A{520,999999999,18,666,88888}数组可能无法开这么大，但只要不考虑它们之间大小的关系就可以和{2,5,1,3,4}等价
  • 即将A[i]与1~N对应起来，
  • 具体做法是按数值从小到大排序，排序完再按照“计算排名”的方式将“排名”根据一个原始序号存入一个新数组

1.数组实现的离散化 

sort(a+1,a+n+1);
m=unique(a+1,a+1+n)-a-1;//m为不重复的元素的个数 
for(int i=1; i<=n; i++) 
b[i]=lower_bound(a+1,a+1+m,b[i])-t;

2.结构体数组实现的离散化 

struct node{
    int val,pos;
}a[maxn];
bool cmp(node a,node b){
    return a.val<b.val;
}
for(int i=1;i<=n;i++){
    cin>>a[i].val;
    a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
    if(i==1||a[i].val!=a[i-1].val)b[a[i].pos]=i;
    else b[a[i].pos]=b[a[i-1].pos];
}

思路与具体做法

  • =0表示数字i在序列中没有出现过
  • !=0表示数字i在序列中出现的次数
  • 这里对树状数组先更新再查询
  • 先更新，;表示的出现次数+1
  • 后查询，代表当前小于等于k[i]的数的个数，代表当前大于k[i]的数的个数
    图片说明 
class Solution {
public:
    priority_queue<long long,vector<long long>,greater<long long> >q;//按数字从小到大排列 
    int lowbit(int x){
        return x&(-x);
    }
    void update(long long i, long long x,vector<long long>&tree,long long n){//单点修改 
        for(long long pos=i;pos<=n;pos+=lowbit(pos))
            tree[pos] += x;
    }
    long long getSum(long long n,vector<long long>&tree){//求前n项和
        long long ans = 0;
        for(long long pos=n;pos;pos-=lowbit(pos))
            ans+=tree[pos];
        return ans;
    }
    long long getNumValidPairs(int n, int m, vector<int>& a) {
        for(int i=0;i<m;i++){
            q.push(0);
        }
        vector<long long>ff(a.size(),0);//新建一个longlong数组保存数组，接着求它的逆序对 
        for(int i=0;i<n;i++){
            long long t=q.top();q.pop();
            ff[i]=t+a[i];
            q.push(ff[i]);
        }         
        vector<long long>s(n+1,0);//离散化，排序，去重的数组 
        vector<long long>k(n+1,0);//原数组在 排序，去重的数组 中的位置 
        vector<long long>tree(n+1,0);//树状数组 
        for(int i=0;i<n;i++){
            s[i+1]=ff[i];
            k[i+1]=s[i+1];
        } 
        sort(s.begin()+1,s.begin()+n+1);
        long long  cn=1,sum=0;        
        vector<long long>::iterator pos = unique(s.begin(), s.end());
        s.erase(pos, s.end());
        int cn2=s.size()-1;
        for(int i=1;i<=n;i++){
            k[i]=lower_bound(s.begin()+1,s.begin()+cn2+1,k[i])-s.begin();
        } 
        for(int i=1;i<=n;i++){
            update(k[i],1,tree,n);//k[i]的出现次数+1
            sum+=(long long)(i-getSum(k[i],tree));//小于等于k[i]的数的个数getSum(k[i],tree)，i-getSum(k[i],tree)即大于k[i]的数的个数
        }
        return sum;
    }
};

时间复杂度和空间复杂度分析

时间复杂度：，一次单点修改和区间查询的时间复杂度都是，进行n次
空间复杂度：，用到了长度为n+1的s，k，tree数组