Inverse Pair

题目大意

给定一个1~n的排列，你可以给其中任意个数加上1，使得到的新序列的逆序对个数尽量少。

思路

由于是一个排列，即每个数仅会出现一次。

我们考虑什么情况下把一个数X加上1之后，会让逆序对减少，那么肯定是这个数的左面存在比它大一的数，此时，把X加一之后，逆序对的数量就会减少1，因为比它大1的数只有一个，在X加上1之后，就与X相等了，比它大2及以上的数，还是比X大，而比X小的数，还是比X小。

具体解法： 我们统计一下存在多少个X，满足比它大1的数在它左面。当然这样的数对只能使用一次。比如 3 2 1，把1加上1之后，就和2相等了，所以此时再把2加1不会使结果增加。求出原本的逆序对，然后减去我们找出的满足条件的数对就可以了。

代码

#include <cstdio>
using namespace std;

const int maxN = 2e5 + 7;
int n, a[maxN], b[maxN], c[maxN], used[maxN];

int ask(int x)
{
    int ans = 0;
    for(; x; x -= x & -x)
        ans += c[x];
    return ans;
}

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] += y;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[a[i]] = i;
    }
    long long revNum = 0;
    for(int i = n; i >= 1; --i) {
        revNum += ask(a[i] - 1);
        add(a[i], 1);
    }
    int minusNum = 0;
    for(int i = 1; i < n; ++i) {
        if(used[i])
            continue;
        if(b[i] > b[i + 1]) {
            used[i] = used[i + 1] = 1;
            minusNum++;
        }
    }
    printf("%lld\n", revNum- 1LL * minusNum);
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/08/04/Inverse-Pair/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！