学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：给定无序的n个数 0~n-1，可以这样变幻得到n的不同的序列：每次将序列中第一个数放到最后一个。

问在这n个序列中逆序对数最少是多少？

思路：

已知逆序对数的定义后，可以直接暴力求原序列的逆序对数，设为sum；可以发现以后n-1个的序列的逆序对数就知道了，不难证明，两个相邻序列的逆序对数差值为 n-1-2*x。

这个题可以直接暴力过，也可以线段树过。一开始是没想到怎么用线段树做。看了题解才明白。

首先建树，节点中有一个num域，如果某个数在该区间中，那么该区间的num值加1。相当于数x在线段树中走一遍，用num来记录它的足迹（个人理解）。每输入一个数x就查询在区间[x+1,n-1]中的num值，也就是在输入x之前比x大的数的个数，正好对应逆序对数的定义。然后再把x插入线段树中。这样就把原序列的逆序对数求出来了。

#include <stdio.h>
#include <string.h>

const int maxn = 5005;

struct line
{
	int l;
	int r;
	int num;
}tree[maxn<<2];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].num = 0;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

//区间求和
int query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
		return tree[v].num;

	int mid = (tree[v].l + tree[v].r)>>1;
	if(r <= mid)
		return query(v*2,l,r);
	else if(l > mid)
		return query(v*2+1,l,r);
	else return query(v*2,l,mid) + query(v*2+1,mid+1,r);
}

void update(int v, int x)
{
	if(tree[v].l <= x && tree[v].r >= x)
		tree[v].num++;		//记录x的踪迹
	if(tree[v].l == tree[v].r)
		return;

	int mid = (tree[v].l+tree[v].r)>>1;
	if(x <= mid)
		update(v*2,x);
	else update(v*2+1,x);
}

int main()
{
	int n;
	int a[maxn];
	while(~scanf("%d",&n))
	{
		build(1,0,n);

		int sum = 0,ans;
		
		//求原序列的逆序对数
		for(int i = 0; i < n; i++)
		{
			scanf("%d",&a[i]);
			if(i != 0)
				sum += query(1,a[i]+1,n);//每输入一个数a[i]，就计算[a[i]+1,n-1]区间中已存在的数的个数
			update(1,a[i]);	//再把a[i]插入线段树中
		}
		
		//求其余n-1个序列的逆序对数，并求出最小值
		ans = sum;
		for(int i = 0; i < n; i++)
		{
			sum += n-1-2*a[i];
			if(ans > sum)
				ans = sum;
		}
		printf("%d\n",ans);
	}
	return 0;
}

暴力解法：

#include <stdio.h>
#include <string.h>
int main()
{
    int n;
    int a[5005];
    while(~scanf("%d",&n))
    {
        long long num = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
            if(i != 0)
            {
                for(int j = i-1; j >= 0; j--)
                {
                    if(a[j] > a[i])
                        num++;
                }
            }
        }
        //printf("%d\n",num);
        long long ans = num;
        for(int i = 0; i < n; i++)
        {
            num = num + n-1-2*a[i];
            if(ans > num)
                ans = num;
        }
        printf("%lld\n",ans);

    }
    return 0;
}