Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P1966 [NOIP2013 提高组] 火柴排队

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟
标签：            

P1966 [NOIP2013 提高组] 火柴排队

$$
\sum (a _ i - b _ i) ^ 2 = \sum (a _ i ^ 2 + b _ i ^ 2) - 2\sum a _ i b _ i
$$
即需要考虑最大化 $\sum a _ i b _ i$ 。考虑两个序列升序序列 $a _ 1, a _ 2, \ldots, a _ n$ 和 $b _ 1, b _ 2, \ldots, b _ n$ ，若交换 $i, j$ ，贡献变化为：
$$
a _ i b _ j + a _ j b _ i - a _ i b _ i - a _ j b _ j = (a _ i - a _ j) (b _ j - b _ i)
$$
$a _ i - a _ j$ 和 $b _ j - b _ i$ 中必有一个负数，故贡献减少。故可以归纳证明，满足答案的序列需要满足第 $k$ 大的 $a$ 与第 $k$ 大的 $b$ 需要交换在一起。

考虑处理出第 $k$ 大的 $a, b$ 的位置，进一步处理出 $a$ 中第 $i$ 个位置与 $b$ 中的位置 $w _ i$ 对应，最终答案中需要满足 $w _ i = i$ 。现在考虑操作，考虑在二分图上将对应的两侧连线，其中有若干个交叉点，无论交换 $a$ 还是交换 $b$ ，每次的效果是使交叉点减少 $1$ 。交叉点数即为逆序对数。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, mod = 1e8 - 3;
int tr[N];
int n, u[N], v[N], w[N];
void Discretization(int n, int *x)
{
    vector<int> ws;
    for (int i = 0; i < n; i++)
        ws.push_back(x[i]);
    sort(ws.begin(), ws.end());
    static int tmp[N];
    for (int i = 0; i < n; i++)
        tmp[i] = x[i];
    for (int i = 0; i < n; i++)
        x[lower_bound(ws.begin(), ws.end(), tmp[i]) - ws.begin()] = i + 1;
}
void modify (int x)
{
    for (; x <= n; x += x & -x)
        tr[x]++;
}
int query (int x)
{
    int res = 0;
    for (; x; x -= x & -x)
        res += tr[x];
    return res;
}
int main()
{
    read(n);
    for (int i = 0; i < n; i++)
        read(u[i]);
    for (int i = 0; i < n; i++)
        read(v[i]);
    Discretization(n, u), Discretization(n, v);
    for (int i = 0; i < n; i++)
        w[u[i]] = v[i];
    int res = 0;
    for (int i = n; i; i--)
    {
        (res += query(w[i])) %= mod;
        modify(w[i]);
    }
    write(res);
    return 0;
}
相关文章