题解 | #Inverse Pair#

Inverse Pair

https://ac.nowcoder.com/acm/contest/11255/I

I 题题解

思路

题意:通过对 a 中若干个元素 加1(每个元素只能加1次),使得逆序对的数目变少,问逆序对数目 最少可变为几
因为 a 是 1 到 n 的全排列,即 [1,n] 中每个元素均出现且只出现一次
所以 我们每次 加1操作 最多消掉一个逆序对 ,该逆序对 满足 i < j && ai > aj && ai = aj+1
我们把这样的逆序对 称为 "目标逆序对”
所以,我们只需要统计有多少个 目标逆序对就行,刚开始时的逆序对数目 减去 目标逆序对的数目 就是答案

ps: 需注意一种特殊情况:
假设存在 逆序对 : i < j && ai > aj && ai = aj+1
同时也存在 逆序对: j < k && aj > ak && aj = ak + 1
比如 4、3、2
我们对 3 进行加一 操作后,变成了 4、4、2
此时 第二个位置上的数 和 第三个位置上的数 不再构成目标逆序对

Code

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int N = 3e5+10;

struct node{
    int val,pos;
    bool operator < (const node & x) const { return val < x.val ; }
}p[N];
int tr[N];
int n;
ll num;

int lowbit(int x){
    return x & -x;
}

void add(int x){
    for(int i=x;i<=N;i+=lowbit(i)) tr[i]++;
}

int query(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;  cin>>x;
        p[i]={x,i};
        add(x);
        num+=i-query(x); // 树状数组求逆序对
    }
    sort(p+1,p+1+n);

    for(int i=1;i<n;i++)  if(p[i].pos>p[i+1].pos) num--,i++; // 避免出现上述的特殊情况,从而多减
    cout<<num<<endl;

    return 0;
}
全部评论

相关推荐

喜欢走神的孤勇者练习时长两年半:爱华,信华,等华,黑华
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-21 17:16
科大讯飞 算法工程师 28.0k*14.0, 百分之三十是绩效,惯例只发0.9
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务