首页 > 代码库 > hdu 1394 Minimum Inversion Number
hdu 1394 Minimum Inversion Number
题目链接：hdu 1394 Minimum Inversion Number
该题是求最小逆序对的扩展。可以使用树状数组来实现。对于$n$个数的序列$A$，其第$i$个数($i\in [0,n)$)的逆序数$r_i$可以表示为它的角标$i$减去在它之前且不大于它的数的个数。例如对序列A = {1,3,5,9,0,8,5,7,4,2}中的数,A[8] = 4。其逆序数$r_8 = 8 - 3 = 5$，第二个3表示三个在它前面且比它小的数:{1,3,0}。从而我们可以得到第$i$个数的逆序数公式：
\begin{equation} r_i = i - \sum_{0 \leq j < i And A_j \leq A_i } 1 \end{equation}
对于整个序列$A$有
\begin{equation} R = \sum_{0 \leq i < n}r_i \end{equation}
可以使用树状数组的前i项的和sum(i)函数来快速的计算$\sum_{0 \leq j < i And A_j \leq A_i } 1$，并且使用add(i+1)来对该数进行计数。
得到初始数列的逆序数后，可以轻松地计算变换后序列的逆序数。
如果删除掉第一个数$A_1$，那么逆序数会减小$A_1$。
在把第一个数放到数列结尾，那么逆序数又会增加$n-A_1-1$
从而可以尝试所有的变换方法，最终取最小值即可。
代码如下：
1 #include <cstdlib> 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #define MAXN 5005 6 using namespace std; 7 int bit[MAXN]; 8 int arr[MAXN]; 9 int n;10 int lowbit(int x)11 {12 return x&(-x);13 }14 int sum(int x)15 {16 int ans = 0;17 while( x > 0 )18 {19 ans += bit[x];20 x -= lowbit(x);21 }22 return ans;23 }24 void add(int l, int x)25 {26 while( l <= n )27 {28 bit[l] += x;29 l += lowbit(l);30 }31 }32 int main(int argc, char *argv[])33 {34 while( scanf("%d", &n) != EOF )35 {36 int ans = 0;37 memset(bit, 0, sizeof(bit));38 for( int i = 0 ; i < n ; i++ )39 {40 scanf("%d", &arr[i]);41 ans += i - sum(arr[i]+1);42 add(arr[i]+1, 1);43 }44 int mi = ans;45 for( int i = 0 ; i < n ; i++ )46 {47 ans = ans - arr[i] + n - arr[i] -1;48 mi = ans > mi ? mi : ans;49 }50 printf("%d\n", mi);51 }52 }
hdu 1394 Minimum Inversion Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。