首页 > 代码库 > hdu1394 Minimum Inversion Number(线段树单点更新||暴力)

hdu1394 Minimum Inversion Number(线段树单点更新||暴力)

2024-07-20 12:43:29   221人阅读

题目链接：

huangjing

这个题目暴力和线段树都可以过，但是都需要掌握一个规律。。

当队首元素移到队尾后，可定会减少a[i]个逆序对，然后增加n-1-a[i]个逆序对。
你看比如1移到队尾，那么1>0这个逆序对就会减少，2>1,3>1,4>1这些逆序对就会增加。。
所以发现这个规律就好做了。。

暴力做法就是直接那样模拟。。
线段树做法是首先建立一颗空树，然后插入之前询问这颗树中在[插入元素，n]之间的树，求出来的就是逆序对的个数。然后将其更新进去即可。。

题目：
<marquee width="600">
寻人启事：2014级新生看过来！
</marquee>

Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11157    Accepted Submission(s): 6865


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.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.
 

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
ZOJ Monthly, January 2003
 

Recommend
Ignatius.L   |   We have carefully selected several similar problems for you:  1540 1542 1255 2795 1828 
 

Statistic | Submit | Discuss | Note

代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=5000+10;

int n,ans,cnt;
int a[maxn];

void pre_gao()
{
    cnt=0;
    for(int i=0;i<n-1;i++)
       for(int j=i+1;j<n;j++)
            if(a[i]>a[j])
                cnt++;
}

int main()
{
    while(~scanf("%d",&n))
    {
        ans=INF;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        pre_gao();
        for(int i=0;i<n;i++)
        {
            cnt=cnt-a[i]+n-1-a[i];
            ans=min(ans,cnt);
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
5
5 4 6 7 3
*/

线段树：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=5000+10;

int tree[maxn<<2],n,a[maxn];

void push_up(int dex)
{
    tree[dex]=tree[dex<<1]+tree[dex<<1|1];
}

void buildtree(int l,int r,int dex)
{
    if(l==r)
    {
        tree[dex]=0;
        return;
    }
    int mid=(l+r)/2;
    buildtree(l,mid,dex<<1);
    buildtree(mid+1,r,dex<<1|1);
    push_up(dex);
}

int Query(int L,int R,int l,int r,int dex)
{
    if(L<=l&&R>=r)
        return tree[dex];
    int mid=(l+r)/2;
    if(R<=mid)  return Query(L,R,l,mid,dex<<1);
    else if(L>mid)  return Query(L,R,mid+1,r,dex<<1|1);
    else return Query(L,R,l,mid,dex<<1)+Query(L,R,mid+1,r,dex<<1|1);
}

void Update(int k,int l,int r,int dex)
{
    if(l==r)
    {
        tree[dex]++;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid)  Update(k,l,mid,dex<<1);
    else Update(k,mid+1,r,dex<<1|1);
    push_up(dex);
}

int main()
{
    int cnt,ans;
    while(~scanf("%d",&n))
    {
       cnt=0;
       buildtree(1,n,1);
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&a[i]);
           a[i]=a[i]+1;
           cnt+=Query(a[i],n,1,n,1);
           Update(a[i],1,n,1);
       }
       ans=cnt;
       for(int i=1;i<n;i++)
       {
         cnt=cnt-(a[i]-1)+n-a[i];
         ans=min(ans,cnt);
       }
       printf("%d\n",ans);
    }
    return 0;
}
/*
5
2 3 0 1 4
*/



hdu1394 Minimum Inversion Number(线段树单点更新||暴力)


联系
我们