P1966 [NOIP 2013 提高组] 火柴排队 | 树状数组

题目快照

题目描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$\sum{(a_i - b_i)}$

其中 $ a_i$ 表示第一列火柴中第 i 个火柴的高度，$b_i$ 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

输入格式

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

解题思路

这道题看上去的第一眼思路就是对齐俩个序列的顺序序号
比如 1 2 7 3 与 2 3 7 4 这样的 就能完成题目的要求
那我们总不可能同时操作俩个序列吧，其实固定一个序列，改变一个序列的效果是一样的。
所以我们可以以其中一个序列为主，来改变另一个序列。
又因为高度可能千变万化，但是他们一定有个大小顺序。
所以我们可以先用离散化的思想将序列按照大小编个号 像这样
3 2 1 6 -> 3 2 1 4
4 3 9 8 -> 2 1 4 3
编号好了 我们现在就要第二个序列往第一个序列上凑。
然后我们就可以发现A中第一个数与B中第一个数不一样（顺序不同），那么这就是一个逆序对，这个数不符合原则，我们要想办法把所有的逆序对都找出来。

所以我们再加一个辅助数组，用来检查顺序是否相同。c[b[i]] = a[i]

c[b[1]] = c[2] = a[1] = 3
c[b[2]] = c[1] = a[2] = 2
c[b[3]] = c[4] = a[3] = 1
c[b[4]] = c[3] = a[4] = 4

我们要找到不符合原则的数，只要序列原来对应的数是符合要求的，他们编号相同，那么我们排完序两数的相对位置不发生改变，因此不会产生逆序。 反之如果不符合要求，就会产生逆序。

其实这么做是为了给b数组重新确定相对大小关系，样例中数组b中的第二个最终要与数组a的第3个位置对应，故有C[2] = 3。c[1] ~ c[4]: 2 3 4 1（对照着a/b数组更好理解）
a：3 2 1 6 | b：4 3 9 8 （b中的第三个对应a中的第四个 （最大对最大））
如果还不明白，可以举例慢慢理解~

AC code

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int num, val;
}a[100050], b[100050];

int tree[100050], c[100050], n;
bool cmp(node a, node b){
    if(a.val == b.val) return a.num < b.num;
    else return a.val < b.val;
}

void updata(int x, int val){
    for(; x <= n; x += x & (-x)){
        tree[x] += val;
    }
}

int query(int x){
    int sum = 0;
    for(; x > 0; x -= x & (-x)){
        sum += tree[x];
    }
    return sum;
}

int main(){
    cin >> n;
    // 录入第一盒火柴
    for(int i = 1; i <= n; i++){
        cin >> a[i].val;
        a[i].num = i;
    }

    // 录入第二盒火柴
    for(int i = 1; i <= n; i++){
        cin >> b[i].val;
        b[i].num = i;
    }

    // 排序得到新的序列
    // 如 3 2 1 6 -> 3 2 1 4
    //    4 3 9 8 -> 2 1 4 3
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);

    // 大小映射
    // c[b[i]] = a[i]
    // c[b[1]] = c[2] = a[1] = 3
    // c[b[2]] = c[1] = a[2] = 2
    // c[b[3]] = c[4] = a[3] = 1
    // c[b[4]] = c[3] = a[4] = 4
    // 正常顺序 c[1] ~ c[4]: 2 3 4 1
    // 逆序数为： 1 + 1 + 1 = 3
    // 故最少交换次数为 3
    for(int i = 1; i <= n; i++){
        c[b[i].num] = a[i].num;
    }

    long long ans = 0;
    for(int i = 1; i <= n; i++){
        updata(c[i], 1);
        ans += i - query(c[i]);
    }

    cout << ans % (99999997);
    return 0;
}