|
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1484
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给出0 ~ N-1 (1 <= N <= 5000) 的一个排列, 经过循环移位,一共有N个排列,
问这N个排列中逆序对数目最小的。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
树状数组
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
树状数组求逆序数有一个经典算法,把数字大小对应到树状数组的小标,然后
从后往前遍历每个数字,统计比这个数字小的数的个数,然后将这个数插入到树状
数组中,遍历完毕,累加和就是该序列的逆序对的数目。
这题要求序列循环移位n次,每次移位统计一次逆序对,最后得到最小的,如果
按照前面的算法,最好的情况是O(n^2log(n)),所以需要找到一些技巧,将复杂度
降下来,我们发现以下两个数列:
1. a1, a2, , an-1, an
2. a2, a3, , an, a1
第二个是第一个循环左移一位的结果,如果将第一个序列的逆序数分情况讨论就是
S = A + B;其中A = (a2~an)本身的逆序对数目;B = a1和(a2~an)的逆序对数目;
而第二个序列中则是S' = A + B';其中B' = (n-1) - B,于是S和A如果已知,那么
就可以轻松求得S' = A + (n-1) - (S - A)。这样一来,只要知道前一个序列的逆
序数,下一个序列就可以在O(1)的时间内求得。只要每次更新S 和 A 的值即可。
更加一般化的,S表示当前序列的逆序数对数,A表示比当前数小的数的个数,
题目中数列是一个排列,所以A的值其实就是当前值减一。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 5001
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
short c[maxn], val[maxn];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int x) {
return x & (-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void add(int pos) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos <= n) {
c[pos] ++;
pos += lowbit(pos);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int sum(int pos) {
int s = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d", &n) != EOF) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
val[i] = x + 1;
}
for(i = 1; i <= n; i++)
c[i] = 0;
int ans = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = n; i >= 1; i--) {
int x = sum(val[i] - 1);
add(val[i]);
ans += x;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int Min = ans;
int A = val[1] - 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 2; i <= n; i++) {
ans = ans - A + (n-1-A);
A = val[i] - 1;
if(ans < Min)
Min = ans;
}
printf("%d\n", Min);
}
return 0;
}
|