首页 > 其他 > 详细

hdu 1394 (线段树求逆序数)

时间:2018-07-22 22:10:40      阅读:171      评论:0      收藏:0      [点我收藏+]

题目链接:https://vjudge.net/contest/182746#problem/C

转载于  >>>

 

题意描述:

给你一个有0--n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!

 

解题分析:

先利用线段树求出初始序列的逆序数,这里有一个非常巧妙的地方,由于比a[i]大的数是离散且连续的,所以可以用线段树来实现(与线段树节点的区间特性符合)。

 

#include<iostream>
using namespace std;
#define N 5005
struct
{
    int l, r;
    int num;
}tree[4 * N];

void creat(int i, int l, int r)           //初始化该线段树
{
    int mid = (l + r) / 2;
    tree[i].l = l;
    tree[i].r = r;
    tree[i].num = 0;
    if (l == r)
    {
        return;
    }
    creat(i * 2, l, mid);
    creat(i * 2 + 1, mid + 1, r);
}

void updata(int i, int k)
{
    if (tree[i].l == k && tree[i].r == k)
    {
        tree[i].num = 1;
        return;
    }
    int mid = (tree[i].l + tree[i].r) / 2;
    if (k <= mid)
        updata(i * 2, k);
    else
        updata(i * 2 + 1, k);
    tree[i].num = tree[i * 2].num + tree[i * 2 + 1].num;           //trees[i].num表示符合[trees[i].l,trees[i].r]区间的数的个数        
}

int getsum(int i, int k, int n)                       //这个函数不太明白怎么实现的
{
    if (k <= tree[i].l&&tree[i].r <= n)
    {
        return tree[i].num;
    }
    else
    {
        int mid = (tree[i].l + tree[i].r) / 2;
        int sum1 = 0, sum2 = 0;
        if (k <= mid)
            sum1 = getsum(i * 2, k, n);
        if (n>mid)
            sum2 = getsum(i * 2 + 1, k, n);
        return sum1 + sum2;
    }
}
int main()
{
    int n;
    while (scanf("%d", &n)>0)
    {
        int a[N];
        creat(1, 0, n - 1);
        int i;
        int ans = 0;
        for (i = 0; i<n; i++)
        {
            scanf("%d", &a[i]);
            ans += getsum(1, a[i] + 1, n - 1);           //a[i]+1~n-1代表比a[i]大的数,getsum()函数的作用是计算该序列前面有几个数比他大(因为此时只输入了它前面的数)
            updata(1, a[i]);
        }
        int minx = ans;
        for (i = 0; i<n; i++)         //总共要将n个数全部移动一次到序列的最末端
        {
            ans = ans + n - 2 * a[i] - 1;         //当a[i]由第一个变为最后一个时,要加上a[i]后面大于a[i]的数的个数,有n-1-a[i]个,要
            if (ans<minx)                    //减去a[i]后面小于a[i]的数的个数,有a[i]个(注意i是从0开始的)
                minx = ans;
        }
        printf("%d\n", minx);
    }
    return 0;
}

 

 

 

 

2018-07-22

hdu 1394 (线段树求逆序数)

原文:https://www.cnblogs.com/00isok/p/9351602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!