Hdu P1394 Minimum Inversion Number

题目翻译：

约定数字序列a1,a2,...,an的反转数是满足i<j和ai>aj的数对(ai，aj)的数量。

对于给定的数字序列a1,a2,...,an，如果我们将第1到m个数字移动到序列的末尾，我们将获得另一个序列（m>=0，当m=0时就不移动任何数）。这样，总共就会有n个序列，如下：

a1，a2，...，an-1，an （其中m = 0，即初始序列）
a2，a3，...，an，a1 （其中m = 1）
a3，a4，...，an，a1，a2 （其中m = 2）
...
an，a1，a2，...，an-1 （其中m = n-1）
输出这n个序列中反转数最小的序列的反转数。

（根据Google网页翻译整理而成）

思路：

这道题我是用权值线段树来做的，所谓权值线段树，就是维护一个计数数组，类似于桶排序中的桶，而不是维护一个序列。这道题中，我们可以从1到n依次在线段树中插入ai，如果ai=233就在第233个位置上上+1，如果ai=666就在第666个位置上+1......然后统计前面的数有多少是大于ai的，也就是[ai+1,n]，累加到答案里就好了。

但是题目中要求的不只是初始序列啊？难道要每个不同的序列都算一遍？不不不，我们观察一下题目中列举的那几个序列，可以发现，其实每一个序列都是把前一个序列中的第一个数放到最后形成的。那么既然是从第一位移到最后一位，那就很好办了。假设这个要移动的数是x吧，当x移到后面之后，答案减少的数量就是x-1，因为x移动前是第一位，所以移动前所有的比它小的数都可以和它组成题目中的合法数对啊，但这样一移动，这些方案就没有了；答案增加的数量就是n-x，因为x移动后是第最后一位，所以移动后所有的比它大的数都可以和它组成题目中的合法数对，这样一移动，就新增加了这些方案。这样就可以每次都从前一个序列的反转数算出当前序列的反转数，从而提高程序效率了。

时间复杂度：O(Tnlogn)。

（T为数据组数）

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

    using namespace std;

    int s[5005],tree[20005];

//线段树板子

void add(int p,int l,int r,int x)

{

    if(l==r) { tree[p]++; return; }

    int mid=(l+r)>>1;

    if(x<=mid) add(p<<1,l,mid,x);

          else add((p<<1)+1,mid+1,r,x);

    tree[p]=tree[p<<1]+tree[(p<<1)+1];

}

int ask(int p,int l,int r,int x,int y)

{

    if(l==x&&r==y) return tree[p];

    int mid=(l+r)>>1;

    if(y<=mid) return ask(p<<1,l,mid,x,y);

    if(x>mid) return ask((p<<1)+1,mid+1,r,x,y);

    return ask(p<<1,l,mid,x,mid)+ask((p<<1)+1,mid+1,r,mid+1,y);

}

int main()

{

    int n=0;

    while(~scanf("%d",&n))

    {

        memset(tree,0,sizeof(tree));//记得初始化

        int ans=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&s[i]),s[i]++;

            add(1,1,n,s[i]);

            if(s[i]<n) ans+=ask(1,1,n,s[i]+1,n);//注意不要越界

        }

        int anss=ans;

        for(int i=1;i<=n-1;i++)

        {

            ans=ans-(s[i]-1)+(n-s[i]);//由前一个序列转到当前序列

            anss=min(anss,ans);

        }

        printf("%d\n",anss);

    }

    return 0;

}

巴特西

Hdu P1394 Minimum Inversion Number | 权值线段树

最新文章

热门文章