hdu1394

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

18 9月 2015

Minimum Inversion Number

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

1 3 6 9 0 8 5 7 4 2

Sample Output

Author

CHEN, Gaoli

Source

ZOJ Monthly, January 2003

题目类型：线段树

算法分析：先求出初始序列的逆序对数，然后对于后面的序列可以通过递推得到，这是因为每次都是将第一个数取出来放到最后，则可以知道取出这个数会使总的逆序对数损失aa[i]个，而放到最后会使总的逆序对数增加n - aa[i] - 1个

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e4 + 66;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

LL sum[maxn<<2];

void PushUp (int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void UpDate (int rt, int l, int r, int v)
{
    if (l == r)
    {
        sum[rt]++;
        return ;
    }

    int m = (l + r) >> 1;
    if (v <= m)
        UpDate (lson, v);

    else
        UpDate (rson, v);

    PushUp (rt);
}

LL Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return sum[rt];

    int m = (l + r) >> 1;
    LL res = 0;
    if (L <= m)
        res += Query (lson, L, R);

    if (m < R)
        res += Query (rson, L, R);

    return res;
}

int aa[maxn];

int main()
{
//    CPPFF;
    int n;
    while (cin >> n)
    {
        LL res = 0, minval = INF;
        memset (sum, 0, sizeof (sum));
        for (int i = 1; i <= n; i++)
        {
            cin >> aa[i];
            res += Query (1, 0, n - 1, aa[i] + 1, n - 1);
            UpDate (1, 0, n - 1, aa[i]);
        }
        minval = min (minval, res);

        for (int i = 1; i <= n; i++)
        {
            res += n - aa[i] - aa[i] - 1;
            minval = min (minval, res);
        }
        cout << minval << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e4 + 66;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

LL sum[maxn<<2];

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void UpDate (int rt, int l, int r, int v)

{

if (l == r)

{

sum[rt]++;

return ;

}

int m = (l + r) >> 1;

if (v <= m)

UpDate (lson, v);

else

UpDate (rson, v);

PushUp (rt);

}

LL Query (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

return sum[rt];

int m = (l + r) >> 1;

LL res = 0;

if (L <= m)

res += Query (lson, L, R);

if (m < R)

res += Query (rson, L, R);

return res;

}

int aa[maxn];

int main()

{

// CPPFF;

int n;

while (cin >> n)

{

LL res = 0, minval = INF;

memset (sum, 0, sizeof (sum));

for (int i = 1; i <= n; i++)

{

cin >> aa[i];

res += Query (1, 0, n - 1, aa[i] + 1, n - 1);

UpDate (1, 0, n - 1, aa[i]);

}

minval = min (minval, res);

for (int i = 1; i <= n; i++)

{

res += n - aa[i] - aa[i] - 1;

minval = min (minval, res);

}

cout << minval << endl;

}

return 0;

}

hdu1512

hdu2795

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

hdu1394

Minimum Inversion Number

分类目录

标签云

书签

近期评论