我是靠谱客的博主 怕孤单方盒,这篇文章主要介绍Minimum Inversion Number HDU-1394,现在分享给大家,希望可以做个参考。

题目:https://vjudge.net/problem/HDU-1394

题目大意

给定一个序列,将前m(0-n-1)个数字移到末尾,得到一个新的序列。求所有这些序列的逆序的最小值

分析

如果知道了当前序列逆序数为sum,那么移动头元素后的逆序数将会是sum-x+(n-1-x), 那么就是怎么求当前逆序数,自然就用到了线段树。

代码

复制代码
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
109
110
111
112
113
114
115
116
117
118
119
120
121
/******************************************************************** * File Name: hdu1394.cpp * Author: Sequin * mail: Catherine199787@outlook.com * Created Time: 三 9/27 11:29:02 2017 *************************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <ctype.h> #include <set> #include <vector> #include <cmath> #include <bitset> #include <algorithm> #include <climits> #include <string> #include <list> #include <cctype> #include <cstdlib> #include <fstream> #include <sstream> using namespace std; #define lson node << 1 #define rson node << 1 | 1 #define LS l,mid,lson #define RS mid+1,r,rson #define UP(i,x,y) for(i=x;i<=y;i++) #define DOWN(i,x,y) for(i=x;i>=y;i--) #define MEM(a,x) memset(a,x,sizeof(a)) #define W(a) while(a) #define gcd(a,b) __gcd(a,b) #define pi acos(-1.0) #define pii pair<int,int> #define ll long long #define MOD 1000000007 #define INF 0x3f3f3f3f #define EXP 1e-8 #define lowbit(x) (x&-x) ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} #define maxn 5005 int segTree[maxn << 2]; int num[maxn]; void build(int l, int r, int node) { if(l == r) { segTree[node] = 0; } else{ int mid = (l + r) >> 1; build(LS); build(RS); } } int query(int a, int b, int l, int r, int node) { if(l >= a && r <= b) { return segTree[node]; } int re = 0; int mid = (l + r) >> 1; if(a <= mid) { re += query(a, b, LS); } if(mid < b) { re += query(a, b, RS); } return re; } void update(int index, int l, int r, int node) { if(l == r) { segTree[node]++; return; } int mid = (l + r) >> 1; if(index <= mid) { update(index, LS); } else{ update(index, RS); } segTree[node] = segTree[lson] + segTree[rson]; } int main() { int n; while(cin >> n) { MEM(segTree, 0); build(0, n-1, 1); for(int i = 0; i < n; i++) { cin >> num[i]; } int ret = 0; for(int i = 0; i < n; i++) { ret += query(num[i], n-1, 0, n-1, 1); update(num[i], 0, n-1, 1); } int ans = ret; for(int i = 0; i < n; i++) { ret = ret - num[i] + n - num[i] - 1; ans = min(ret, ans); } cout << ans << endl; } return 0; }

最后

以上就是怕孤单方盒最近收集整理的关于Minimum Inversion Number HDU-1394的全部内容,更多相关Minimum内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(85)

评论列表共有 0 条评论

立即
投稿
返回
顶部