hdu-1394 求逆序数

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/42213265

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

首先建立空树，将 a[i] 逐个插入

计算一个序列n排列的最小逆序数

首先用线段树算出出事序列的逆序数，然后找规律推出排列的最小逆序数。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <sstream>
#include <time.h>
#include <utility> 
#include <malloc.h> 

using namespace std;

#define Max 5010

int a[5010];
int n;
int ans;
int sum;

struct
{
    int left;
    int right;
    int num;
}b[4 * Max];

void build(int left, int right, int i)//建立空树
{
    b[i].right = right;
    b[i].left = left;
    b[i].num = 0;

    if (b[i].left == b[i].right)
        return;

    int mid = (left + right) / 2;
    build(left, mid, i * 2);
    build(mid + 1, right, i * 2 + 1);
}

void update(int value, int i)//更新第value个节点， 从跟节点1开始更新到叶子节点value
{
    if (b[i].left == value && b[i].right == value)
    {
        b[i].num = 1;
        return;
    }
    int mid = (b[i].left + b[i].right) / 2;

    if (value <= mid)
        update(value, i * 2);//左子树
    else
        update(value, i * 2 + 1);//右子树

    b[i].num = b[i * 2].num + b[i * 2 + 1].num;//更新根节点
}

int query(int id ,int n,int i)//计算有多少个
{
    if (id <= b[i].left  && b[i].right <= n)
    {
        return b[i].num;
    }
    else
    {
        int mid = (b[i].left + b[i].right)/2;
        int ans1 = 0,ans2 =0;
        if (id <= mid)
        {
            ans1 = query(id, n, i * 2);
        }
        if (mid < n)
        {
            ans2 = query(id, n, i * 2 + 1);
        }
        return ans1 + ans2;
    }
}

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        build(0,n-1,1);
        ans = 0; sum = 0;

        for (int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
            sum += query(a[i]+1,n-1,1);//计算比a[i]大的个数
            update(a[i],1);//更新a[i]
        }

        ans = sum;
        //printf("%d\n", ans);
        for (int i = 0; i < n; i++)
        {
            sum = sum + (n - a[i] -1) - (a[i]);//当把第一个数移到最后一位，
            ans = min(sum, ans);               //比他大的有 n - a[i] + 1 个，比他小的有a[i]个（下标从 0 开始）
        }

        printf("%d\n",ans);
    }
    return 0;
}