继续树状数组 1394

题目大意为：一个从a1到给顶一个an的数组，如果存在两个数（ai，aj）如果满足i<j并且ai>aj，那么就称其为一个逆序数，可以一次把第一个数移到最后面，为一个新的序列，求给定一个序列，其所有情况的最小逆序数个数。
可以分别确定每一个序列的逆序数个数，一个序列的逆序数个数需要从每一个数都进行判断，判断当前的数（假设ai）后面的小于ai的数的个数，储存在ai中做参数，那么所有的a1到an的参数和即为该序列的逆序数个数。
可以假设有4个数：
3 2 1 4
首先代入4，S[4]==0,将0返回，并将C[4]记为1，代入1，S[1]==0,将0返回,C[1]记为1。代入2，前面的小于2的数只有1个，S[2]==1,将1返回，C[2]记为1。代入3，S[3]==2,将2返回，记C[3]为1。
可以总结：先将树状数组初始化为0，从右到左遍历，求得S[i]之和就是总的逆序数的和，遍历完以后自增1。
又是前n项求和的运算，便很自然地想到树状数组：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define MMAX 5005

int C[5005];

int sum(int i)
{
    int ans=0;
    while (i>0)
    {
        ans+=C[i];
        i-=lowbit(i);
    }
    return ans;
}

void add(int i,int k)
{
    while (i<=MMAX)
    {
        C[i]+=k;
        i+=lowbit(i);
    }
}

void main()
{
    int a[MMAX]={0};
    int i,j,k=0,n,m;
    scanf("%d",&n);
    m=n;
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (i=n;i>=1;i--)
    {
        k+=sum(a[i]);
        add(a[i],1);
    }
    printf("%d\n",k);
}

这只是一个序列的求解逆序数，那么当该序列发生了改变之后呢？
我们可以依次移动一个数据来得到一系列的数字值，记下最下的值，该值就是最终所求的解。
假设移动一个值，a[i]，减去a[i]之后，ai后面有ai个比其小的数，ai放在最后其前面有n-1-ai个比其大的数，所以有k=k-a[i]+(n-1-a[i]);

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define MMAX 5010

int C[5010];

int sum(int i)
{
    int ans=0;
    while (i>0)
    {
        ans+=C[i];
        i-=lowbit(i);
    }
    return ans;
}

void add(int i,int k)
{
    while (i<=MMAX)
    {
        C[i]+=k;
        i+=lowbit(i);
    }
}

void main()
{
    int a[MMAX]={0};
    int i,j,k=0,n,m;
    while (scanf("%d",&n)!=EOF&&n!=0)
    {
        
        memset(C, 0, sizeof(C));
        memset(a,0,sizeof (a));
        k=0;
    m=n;
    for (i=0;i<n;i++)
        scanf("%d",&a[i]);
    for (i=n-1;i>=0;i--)
    {
        k+=sum(a[i]+1);
        add(a[i]+1,1);
    }
    int ans=k;
    for(i=0;i<n;i++)
    {
        k+=n-(a[i]<<1)-1;
        if(k<ans)ans=k;
    }
        printf("%d\n",ans);
    }
}