python

5.3 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`P1966` 火柴排队

一、题目描述

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

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

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

输入格式

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

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

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

输出格式

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

样例 #1

样例输入 #1

4
2 3 1 4
3 2 1 4

样例输出 #1

样例 #2

样例输入 #2

4
1 3 4 2
1 7 2 4

样例输出 #2

提示

【输入输出样例说明一】

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

【输入输出样例说明二】

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

【数据范围】

对于 10\% 的数据， 1 \leq n \leq 10；

对于 30\% 的数据，1 \leq n \leq 100；

对于 60\% 的数据，1 \leq n \leq 10^3；

对于 100\% 的数据，1 \leq n \leq 10^5，0 \leq 火柴高度 < 2^{31}。

二、分析题意

首先对计算式进行转化: $\large \displaystyle \ \ \ \ \sum_{i=1}^{n}(a_i-b_i)^2 \ = \sum_{i=1}^n(a_i^2+b_i^2-2a_ib_i) \ = \sum_{i=1}^n(a_i^2+b_i^2) - \sum_{i=1}^n(2a_ib_i) $

可以发现,\large \displaystyle \sum_{i=1}^n(a_i^2+b_i^2)不会被排列顺序所影响。所以，欲使原式最小，只需要使\large \displaystyle \sum_{i=1}^n(2a_ib_i)尽量大即可。

有一个结论：使\large b_i为\large b数组中第i大，使\large a_i为\large a数组中第i大时，对应位置相乘后的和最大。

证明进行反证，假设有：\large a_1<a_2,\large b_1<b_2 设存在\large a_1b_1+a_2b_2<a_1b_2+a_2b_1 则有： \large a_1(b_1-b_2)<a_2(b_1-b_2) 因为\large b_1-b_2<0,则有a_1>a_2 产生矛盾，得以反证,原结论正确。

三、算法实现

先对两数组进行离散化,

由于要将 b 数组作为标准 , 来改变 a 数组的顺序所以对离散化后数组建立映射 , 把b数组当前排列顺序 , 当做一个升序排列的数列即: 使 b_1⇒1,b_2⇒2,b_3⇒3;

由于都已进行了离散化,再将 a 数组中的数进行更改, 按照映射关系, 为它们赋新值. 即: 使 a_1⇒b_i⇒j

然后需要将重赋值的 a 数组进行处理. 由于交换方式为相邻两元素交换即冒泡排序,所以将其变为有序数列的代价 , 即数列中逆序对数. 使用归并排序 / 树状数组求逆序对即可

`Code`

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

const int N = 100010;
const int mod = 99999997;

struct Node {
    int x, pos;
    const bool operator<(const Node &t) const {
        return x < t.x;
    }
} a[N], b[N];

int n;
int q[N];
LL ans;

// 树状数组
int c[N];
#define lowbit(x) (x & -x)
void add(int x, int v) {
    while (x < N) c[x] += v, x += lowbit(x);
}

LL sum(int x) {
    LL res = 0;
    while (x) res += c[x], x -= lowbit(x);
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P1966.in", "r", stdin);
#endif
    scanf("%d", &n); // 火柴的数目

    // 记录第一列火柴的高度，火柴的序号
    for (int i = 1; i <= n; i++) scanf("%d", &a[i].x), a[i].pos = i;
    // 记录第二列火柴的高度，火柴的序号
    for (int i = 1; i <= n; i++) scanf("%d", &b[i].x), b[i].pos = i;

    // 使用高度这个概念，进行由小到大排序
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    // 高度概念消费完毕，只能继续使用位置这个概念了
    // 将一个二维的逆序对问题，转化为一维逆序对问题
    // a[1].pos : 第一列中高度最小的火柴所在位置
    // b[1].pos : 第二列中高度最小的火柴所在位置
    // 两者之间为什么需要建立起关联？两者之间如何建立成关联？
    // 可以理解为: 以前 Japan那道题，出现了多条相交的边，需要把它们梳理成互相不相交的边
    // 以b为标准，将a进行调整
    for (int i = 1; i <= n; i++) q[a[i].pos] = b[i].pos; // 类似于离散化

    for (int i = 1; i <= n; i++) {
        ans = (ans + sum(n) - sum(q[i])) % mod;
        add(q[i], 1);
    }
    // 输出结果
    printf("%lld", ans);
    return 0;
}

5.3 KiB Raw Permalink Blame History Unescape Escape

P1966 火柴排队