HDU-1369-Minimum Inversion Number（树状数组|线段树，求逆序数）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
| Problem Description The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
Input The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output For each case, output the minimum inversion number on a single line.
Sample Input
10 1 3 6 9 0 8 5 7 4 2
Sample Output
16
Author CHEN, Gaoli
Source
Recommend Ignatius.L | We have carefully selected several similar problems for you: 1166 1698 1540 1542 1255 |
题目大意：给一个n个数的序列：a1,a2,a3,a4,a5.....an;
让他们进行交换成：
a2,a3,a4...an,a1;
a3,a4,a5.......an,a1,a2
.......
所有的数ai都要在0~n-1之间（很重要，递推式的条件！！！）
n种序列，找出其中最小的那个序列的逆序数的对数；
这道题写的时候是放在线段树里面的，但是用树状数组求逆序数似乎更简单一点，
找到规律，
先求出第一组序列的逆序数，将第一个元素放到后面，相当于
原来的序列减少一个a[i]个逆序数，在后面加上n-a[i]-1(减去它本身)个逆序数
处理出一组逆序数，然后递推找最小的，
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define clean(a,b) memset(a,b,sizeof(a))// 水印
int tree[5010];
int arr[5010];
int n;
int lowbit(int i)
{
return i&(-i);
}
void updata(int i)
{
while(i<=n)
{
tree[i]=tree[i]+1;
i=i+lowbit(i);
}
}
ll Query(int i)
{
ll res=0;
while(i>0)
{
res=res+tree[i];
i=i-lowbit(i);
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
clean(arr,0);
clean(tree,0);
ll ans=0;
for(ll i=1;i<=n;++i)
{
scanf("%d",&arr[i]);
updata(arr[i]+1);
ans=ans+i-Query(arr[i]+1);//逆序数的数量
//cout<<arr[i]<<" ";
}
ll res=ans;
for(ll i=1;i<=n;++i)
{
ans=ans+(n-arr[i]-1)-arr[i];
if(res>ans)
res=ans;
}
cout<<res<<endl;
}
}
//树状数组很简单，但毕竟是放在线段树里面的，就用线段树再写一份把：
ac：
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define clean(a,b) memset(a,b,sizeof(a))// 水印
int tree[5010<<2];//一个树的空间
int arr[5010];
void updata(int x,int l,int r,int rt)
{
if(l==r)
{
tree[rt]++;
return ;
}
int mid=(r+l)>>1;
if(x<=mid)
updata(x,l,mid,rt<<1);
else
updata(x,mid+1,r,rt<<1|1);
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
int Query(int L,int R,int l,int r,int rt)
{
//cout<<rt<<" "<<tree[rt]<<endl;
if(L<=l&&r<=R)
return tree[rt];
int mid=(r+l)>>1;
int res=0;
if(L<=mid)
res=res+Query(L,R,l,mid,rt<<1);
if(R>mid)
res=res+Query(L,R,mid+1,r,rt<<1|1);
return res;
}
//void build_tree(int l,int r,int rt)
//{
// if(l==r)
// {
// cout<<tree[rt]<<" ";
// return ;
// }
// int mid=(r+l)>>1;
// build_tree(l,mid,rt<<1);
// build_tree(mid+1,r,rt<<1|1);
//
//}
int main()
{
int n;
while(cin>>n)
{
clean(tree,0);
clean(arr,0);
int ans=0;
for(int i=1;i<=n;++i)
{
cin>>arr[i];
updata(arr[i]+1,1,n,1);//从根节点找,+1避免出现0
ans=ans+Query(arr[i]+2,n,1,n,1);
}
//build_tree(1,n,1);//调试
int res=ans;
for(int i=1;i<=n;++i)
{
//cout<<ans<<" ";
ans=ans+(n-2*arr[i]-1);
if(res>ans)
res=ans;
}
cout<<res<<endl;
}
}
