翻车笔记_ Noip2010Day1T2 火柴排队 [逆序对, 数学]

这个题不错…纪念一下

懵逼的 题目

传送至 Vijos

扯淡的 题解

一开始和很多人想的一样:

  • 使用一个结构体包含两个变量A, B
  • 按照先A, 后B的顺序排序
  • 在B中找逆序对

但是错了

需要注意的是调换顺序不是在排完序的序列里调换的, 而是在原序列中调换的!
辣鸡样例居然能过
所以我们需要的是让B数组和A数组在原序列中一一对应起来, 而非在排完序的序列中再操作
想明白这个这个题就比较简单了:

  • 先在原序列中记录A数组中每个数的位置
  • 然后给A, B分别排序, 找到A与B之间每个元素的对应关系
  • 然后把B恢复原状, 把Bi替换成 [ 排序后的序列中与Bi对应的Ai 在原序列中的编号]
  • 求逆序对
    结束, AC

还有就是为什么两个序列对应的时候费用最小:

  • (a - b) ^ 2 = a ^ 2 - 2ab + b ^ 2
  • sigma a ^ 2 + b ^ 2 肯定不变, 因为序列的元素没变
  • 所以当 -2ab 最小的时候, sigma (a - b) ^ 2 最小
  • 根据正方形面积大于周长相等长方形的面积, 当 a 与 b 接近时, ab最大, -2ab最小
    结束, 得证

沙茶的 代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define MOD (99999997)
using namespace std;
struct xl
{
int a;
int bh;
}ma[MAXN], mb[MAXN];
int n;
int ans;
int b[MAXN];
int t[MAXN];
void init();
//void mmerge(int, int);
void work(int, int);
bool cmp(xl, xl);
void solve();
int main()
{
init();
solve();
printf("%d", ans);
return 0;
}
void init()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &ma[i].a);
ma[i].bh = i;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &mb[i].a);
mb[i].bh = i;
}
}
void solve()
{
sort(ma + 1, ma + n + 1, cmp);
sort(mb + 1, mb + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
b[mb[i].bh] = ma[i].bh;
}
work(1, n);
}
void work(int le, int ri)
{
if (le < ri)
{
int mi = (le + ri) >> 1;
work(le, mi);
work(mi + 1, ri);
int i = le, j = le, k = mi + 1;
while(i <= ri && j <= mi && k <= ri)
{
if (b[j] > b[k])
{
ans += mi - j + 1;
ans %= MOD;
t[i++] = b[k++];
}
else
{
t[i++] = b[j++];
}
}
for (; j <= mi; j++)
{
t[i++] = b[j];
}
for (; k <= ri; k++)
{
t[i++] = b[k];
}
for (int z = le; z <= ri; z++)
{
b[z] = t[z];
}
}
}
bool cmp(xl x, xl y)
{
if (x.a == y.a)
{
return x.bh < y.bh;
}
else
{
return x.a < y.a;
}
}

/*
4
2 3 1 4
3 2 1 4


1
*/

By 因为没写作业站了一节课神清气爽的 Cansult