HDU1394线段树

题目链接hdu1394
题意：给n个数，可以将前m个数放到最后，一共有n种情况，要求这n种情况中，逆序对个数最少数多少。
思路：在每次插入前，使用线段树求出大于当前点的个数。最后在求出每次移动一个数到最后后逆序对打个数。假如原本序列的逆序对个数为m，第一个数为x，那么如果把0移到最后，那么逆序对数目则为m+n-1-2*x
code:

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r

const int maxn = 5500;
int tree[maxn << 2];
int v[maxn];

int query(int rt, int l, int r, int L, int R)
{
    if (l == L && R == r)
        return tree[rt];
    if (R <= mid)
        return query(lson, L, R);
    if (L > mid)
        return query(rson, L, R);
    return query(lson, L, mid) + query(rson, mid + 1, R);
}

void update(int rt, int l, int r, int a)
{
    tree[rt]++;
    if (l == r)
    {
        tree[rt] = 1;
        return;
    }

    if (a <= mid)
        update(lson, a);
    else if (a > mid)
        update(rson, a);
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n)
    {
        memset(tree, 0, sizeof(tree));
        int sum = 0;
        int i, num;
        for (i = 0; i < n; i++)
        {
            cin >> v[i];
            sum += query(1, 1, n, v[i] + 1, n);
            update(1, 1, n, v[i] + 1);
        }
        int ans = sum;
        for (i = 0; i < n - 1; i++)
        {
            sum = sum + n - 1 - 2 * v[i];
            ans = min(ans, sum);
        }
        cout << ans << endl;
    }

    return 0;
}

最后

以上就是害怕故事为你收集整理的HDU1394线段树的全部内容，希望文章能够帮你解决HDU1394线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。