HDU 1394 Minimum Inversion Number（树状数组）

题目大意

给一个 0~n-1 的排列(n≤5000)，可以把这个排列的前 m(0≤m≤n-1) 个数移到排列的最后：如下面的例子所示

a₁, a₂, ..., a_n-1, a_n

a₃, a₄, ..., a_n, a₁, a₂

...

a_n, a₁, a₂, ..., a_n-1

现在问，在这 n 个排列中，逆序数最小的是多少，并输出这个最小逆序数

逆序指的是： i<j && a_i>a_j

做法分析

先考虑怎么求逆序数：树状数组

BIT[i] 记录的是 [i-i&(-i), i] 这个区间中，有多少个数，注意：树状数组的下标不能从 0 开始

那么，每读入一个数 a_i

我们先更新一次： update(a_i+1, 1)

然后求比这个数大的数有多少个： query(n+1)-query(a_i+1)

求和之后便是原始序列中逆序对的个数了

先求出原始序列的逆序数，设为 sum

考虑：每次把序列中第一个数 a₁ 移到序列的末尾，我们应该怎么变换？没错：把整个序列扫描一遍：

如果这个数比 a₁小，那么 sum-- （没有移动之前，他们是一个逆序对，移动之后，不是逆序对了）

如果这个数比 a₁大，那么 sum++ （没有移动之前，他们不是逆序对，移动之后，他们构成了一个逆序对）

这样扫描一遍之后，便得到了当前这个新序列的逆序对的个数，以此统计最小值即可

时间复杂度：o(n²)

参考代码

HDU 1394

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 const int N=5006;
 8 int n, BIT[N], a[N];
 9 
10 void update(int pos, int val)
11 {
12     for(; pos<N; pos+=pos&(-pos)) BIT[pos]+=val;
13 }
14 
15 int query(int pos)
16 {
17     int ans=0;
18     for(; pos>0; pos-=pos&(-pos)) ans+=BIT[pos];
19     return ans;
20 }
21 
22 int main()
23 {
24     int n;
25     while(scanf("%d", &n)!=EOF)
26     {
27         memset(BIT, 0, sizeof BIT);
28         int sum=0;
29         for(int i=0; i<n; i++)
30         {
31             scanf("%d", &a[i]);
32             update(a[i]+1, 1);
33             sum+=query(n+1)-query(a[i]+1);
34         }
35         int ans=sum;
36         for(int i=0; i<n; i++)
37         {
38             for(int j=0; j<n; j++)
39             {
40                 if(a[i]>a[j]) sum--;
41                 if(a[i]<a[j]) sum++;
42             }
43             if(sum<ans) ans=sum;
44         }
45         printf("%d\n", ans);
46     }
47     return 0;
48 }

题目链接 & AC通道

HDU 1394 Minimum Inversion Number