蓝桥杯算法训练-逆序对 解题报告

问题描述

大体意思是,根据输入构建一棵二叉树,其中以其叶子节点从左到右为一数列,为了使得该数列的逆序对最少,可以对每个非叶子节点进行调换左右字数操作,求最少的逆序对。

算法思路

题目标明用平衡二叉树进行处理,可以选择用Splay树或者AVL树进行处理,考虑到之前求逆序对的题目原型一般用归并排序进行,所以这里我打算用归并排序动态规划处理。

由于题目中特殊的树结构,所以将传统的归并排序的二分改为递归到叶子节点,再合并到根节点。根据其最优子结构,要使得整体逆序对最少,也就是每个子树的逆序对最少,以此类推。可以很容易得到递推公式:

f(root) = f(left) + f(right) + min(merge(left , right) , merge(right , left));

合并时的思路为,a[i]和b[j]分别表示两个序列的相应元素,若a[i] > b[j],则a[i]之后的数均大于b[j],因为该序列为从小到大排序的,这样就可以统计逆序对了。

同理可以统计顺序对,顺序对则对应了调换子树后的逆序对,比较顺序对和逆序对的大小,然后求f(root),同时合并序列至根节点。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define MP make_pair
#define mod 1000000007
#define eps 1e-8
#define pi acos(-1.0)
#define inf 0x3fffffff
#define maxn 400005
struct node{
vector<int> v;
LL min;
};
LL ans;
LL maxx=0;
LL maxxx = 0;
int flag = 0;
node merge(node l,node r);
node build_tree(LL i){
// printf("node %d:\n",i);
int x;
scanf("%d",&x);
node t;
t.min = 0;
if(x != 0)
t.v.push_back(x);
else{
node l = build_tree(i+1);
node r = build_tree(i+1);
t = merge(l,r);
}
if(i == 1)
ans = t.min;
return t;
}
node merge(node l,node r){
if(l.v.size() > maxx)
maxx = l.v.size();
if(r.v.size() > maxx)
maxx = r.v.size();
int i = 0 ,j = 0;
LL l_cnt = 0,r_cnt = 0;
vector<int>tmp;
while(i < l.v.size() && j < r.v.size()){
if(l.v[i] == r.v[j]){
tmp.push_back(l.v[i]);
tmp.push_back(r.v[j]);
} else if(l.v[i] < r.v[j]){
r_cnt += r.v.size() - j;
tmp.push_back(l.v[i++]);
} else{
l_cnt += l.v.size() - i;
tmp.push_back(r.v[j++]);
}
}
while(i < l.v.size())
tmp.push_back(l.v[i++]);
while(j < r.v.size())
tmp.push_back(r.v[j++]);
node root;
root.min = l.min + r.min + min(l_cnt,r_cnt);
for(int k = 0; k < tmp.size();k++){
// printf("%d ",tmp[k]);
root.v.push_back(tmp[k]);
}
// printf("\n");
return root;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);//freopen("output.txt","w",stdout);
#endif
LL n;
scanf("%d",&n);
build_tree(1);
cout<<ans<<endl;
}

结果

最后提交OJ的时候发现25组只通过了12组,48分,也就是说该方法还是有问题,理论上复杂度为o(nlogn),但是数据过强,所以待我习得Splay大法后写一份Splay的解法。