[NOIp2013] 火柴排队

发表于 | 分类于 > >
字数统计 : 406   |   阅读时长 ≈ 2 mins.

题目

链接

[NOIp2013]火柴排队

题意简述

有两列共 支火柴

两列火柴之间的距离定义为：

通过交换使得两列火柴之间的距离最小，出这个最小交换次数对 99,999,997 取模。

思路

逆序对

通过数学归纳法 （雾 易发现将两列火柴排序后距离最小。
不接受反驳。
就成了归并排序。
排序后记录对应关系，跑一遍树状数组即可。
时间复杂度： $O(nlogn)$ 。

代码

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e5 + 10, kmax_int = 2147483647, kmod = 99999997;

#define pii std::pair<int, int>
#define mp std::make_pair

int n;
int c[kmax_num];
inline void Add(REG int pos, REG int num)	{ for( ; pos <= n; pos += pos & -pos)	c[pos] += num; return ; }
inline int Sum(REG int pos)	{ REG int ans = 0; for( ; pos; pos -= pos & -pos)	ans += c[pos]; return ans; }

pii num1[kmax_num], num2[kmax_num];
int hash1[kmax_num], hash2[kmax_num];

inline void Mod(REG long long& num) {
    while(num < 0)  num += kmod;
    while(num >= kmod)  num -= kmod;
    return ;
}

int main() {
    std::cin >> n;
    For(i,1,n)	std::cin >> num1[i].first, num1[i].second = i;
    For(i,1,n)	std::cin >> num2[i].first, num2[i].second = i;

    std::sort(num1 + 1, num1 + n + 1), 
    std::sort(num2 + 1, num2 + n + 1);

    For(i,1,n)	hash1[num1[i].second] = num2[i].second;

    REG long long ans = 0;
    For(i,1,n)	{
        Add(hash1[i], 1);
        ans += i - Sum(hash1[i]);
        Mod(ans);
    }
    printf("%lld\n", ans);
    return 0;
}

杂项

  • 这里记录相对位置用了 $std::pair$ 实现，还是 $std::pair$ 大法好！