hdoj 1394 Minimum Inversion Number【線分ツリーor線分ツリーlazy or樹状配列or集計ソート】【逆シーケンスペア】
8878 ワード
Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12991 Accepted Submission(s): 7939
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
Sample Output
題意:1つの数列が知られており、数列個数n<=5000であり、数列中の数の範囲は[0,n-1]であり、数は重複しない.数列の最初の数を移動するたびに
一番後ろには、n個の数列を構築することができます.このn個の数列の中の最小逆シーケンス数を求めます.
(数列の逆順の正しい方法を求めて言わないで、知りたいなら私の前のブログを見てください)
考え方:最初の数列の逆順数を求めた後、同じ操作をして他の数列の逆順対を求める必要はありません(時間は許されません).実は最初の数列の逆序数を計算すれば、他の数列の逆序数はこの計算済みの逆序数で出すことができます.具体的には、1つの数aが一番後ろに移動すると、この数の後ろにn-a-1の数がそれより大きくなり、aの数がそれより小さくなり、移動すると、この数の逆シーケンス数がn-a-1増加し、他の数の逆シーケンス数がa減少するので、現在のシーケンスにとって逆シーケンス数が増加する(n- 1 - a - a).したがって,n回の遍歴だけで他の数列の逆シーケンス対数を求め,更新するたびによい.
私はまず木の配列で書いて、上に注釈があって、後ろの3つは線分の木と並べ替えで書いています.
ツリー配列:62 ms
セグメントツリーlazy単点更新:93 ms
線分ツリー(Lazyを使用しない):62 ms
集計ソート:46 ms(こんなに効率的だとは思わなかったので、マスター)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12991 Accepted Submission(s): 7939
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
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
題意:1つの数列が知られており、数列個数n<=5000であり、数列中の数の範囲は[0,n-1]であり、数は重複しない.数列の最初の数を移動するたびに
一番後ろには、n個の数列を構築することができます.このn個の数列の中の最小逆シーケンス数を求めます.
(数列の逆順の正しい方法を求めて言わないで、知りたいなら私の前のブログを見てください)
考え方:最初の数列の逆順数を求めた後、同じ操作をして他の数列の逆順対を求める必要はありません(時間は許されません).実は最初の数列の逆序数を計算すれば、他の数列の逆序数はこの計算済みの逆序数で出すことができます.具体的には、1つの数aが一番後ろに移動すると、この数の後ろにn-a-1の数がそれより大きくなり、aの数がそれより小さくなり、移動すると、この数の逆シーケンス数がn-a-1増加し、他の数の逆シーケンス数がa減少するので、現在のシーケンスにとって逆シーケンス数が増加する(n- 1 - a - a).したがって,n回の遍歴だけで他の数列の逆シーケンス対数を求め,更新するたびによい.
私はまず木の配列で書いて、上に注釈があって、後ろの3つは線分の木と並べ替えで書いています.
ツリー配列:62 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAX 5000
using namespace std;
int c[MAX<<2];
int n;
struct record
{
int val, pos;
}num[MAX];
bool cmp1(record a,record b)
{
return a.val > b.val;
}
bool cmp2(record a,record b)
{
return a.pos < b.pos;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
while(x <= n)
{
c[x] += 1;
x += lowbit(x);
}
}
int sum(int x)
{
int s=0;
while(x > 0)
{
s += c[x];
x -= lowbit(x);
}
return s;
}
int main()
{
int i, j;
LL ans;//
LL res;//
while(~scanf("%d", &n))
{
memset(c, 0, sizeof(c));
for(i = 0; i < n; i++)
{
scanf("%d", &num[i].val);
num[i].pos = i + 1;
}
sort(num, num+n, cmp1);
ans = 0;
for(i = 0; i < n; i++)
{
update(num[i].pos);
if(num[i].pos == 1)
continue;
ans += sum(num[i].pos - 1);
}
sort(num, num+n ,cmp2);//
res = ans;//
for(i = 0; i < n; i++)
{
res += n - 1 - num[i].val -num[i].val;
ans = min(ans, res);//
}
printf("%lld
", ans);
}
return 0;
}
セグメントツリーlazy単点更新:93 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAX 5000+10
using namespace std;
int sum[MAX<<2];
struct record
{
int val, pos;
}num[MAX];
bool cmp1(record a,record b)
{
return a.val > b.val;
}
bool cmp2(record a,record b)
{
return a.pos < b.pos;
}
void PushUp(int o)
{
sum[o] = sum[o<<1] + sum[o<<1|1];
}
void build(int o, int l, int r)
{
sum[o] = 0;
if(l == r)
return ;
int mid = (l+r) >> 1;
build(o<<1, l , mid);
build(o<<1|1, mid+1, r);
PushUp(o);
}
void update(int o, int l, int r, int L)
{
if(l == r)
{
sum[o] += 1;
return ;
}
int mid = (l+r) >> 1;
if(L <= mid) update(o<<1, l, mid, L);
else update(o<<1|1, mid+1, r,L);
PushUp(o);
}
int query(int o ,int l, int r, int L, int R)
{
if(L <= l && R >= r)
{
return sum[o];
}
int mid = (l+r) >> 1;
int res = 0;
if(L <= mid) res += query(o<<1, l ,mid, L, R);
if(R > mid) res += query(o<<1|1, mid+1, r, L, R);
return res;
}
int main()
{
int n;
int i;
LL ans, res;
while(~scanf("%d", &n))
{
build(1, 1, n);
for(i = 0; i < n; i++)
{
scanf("%d", &num[i].val);
num[i].pos = i + 1;
}
sort(num, num+n, cmp1);
ans = 0;
for(i = 0; i < n; i++)
{
update(1, 1, n, num[i].pos);
if(num[i].pos == 1)
continue;
ans += query(1, 1, n, 1, num[i].pos - 1);
}
res = ans;
sort(num, num+n, cmp2);
for(i = 0; i < n; i++)
{
res += n - 1 - num[i].val - num[i].val;
ans = min(ans, res);
}
printf("%lld
", ans);
}
return 0;
}
線分ツリー(Lazyを使用しない):62 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAX 5000+10
using namespace std;
int sum[MAX<<2];
struct record
{
int val, pos;
}num[MAX];
bool cmp1(record a,record b)
{
return a.val > b.val;
}
bool cmp2(record a,record b)
{
return a.pos < b.pos;
}
void build(int o, int l, int r)
{
sum[o] = 0;
if(l == r)
return ;
int mid = (l+r) >> 1;
build(o<<1, l , mid);
build(o<<1|1, mid+1, r);
}
void update(int o, int l, int r, int L)
{
sum[o] += 1;
if(l == r)
return ;
int mid = (l+r) >> 1;
if(L <= mid) update(o<<1, l, mid, L);
else update(o<<1|1, mid+1, r, L);
}
int query(int o ,int l, int r, int L, int R)
{
if(L == l && R == r)
{
return sum[o];
}
int mid = (l+r) >> 1;
int res = 0;
if(R <= mid) return query(o<<1, l ,mid, L, R);
else if(L > mid) return query(o<<1|1, mid+1, r, L, R);
else return query(o<<1, l, mid, L, mid) + query(o<<1|1, mid+1, r, mid+1, R);
}
int main()
{
int n;
int i;
LL ans, res;
while(~scanf("%d", &n))
{
build(1, 1, n);
for(i = 0; i < n; i++)
{
scanf("%d", &num[i].val);
num[i].pos = i + 1;
}
sort(num, num+n, cmp1);
ans = 0;
for(i = 0; i < n; i++)
{
update(1, 1, n, num[i].pos);
if(num[i].pos == 1)
continue;
ans += query(1, 1, n, 1, num[i].pos - 1);
}
res = ans;
sort(num, num+n, cmp2);
for(i = 0; i < n; i++)
{
res += n - 1 - num[i].val - num[i].val;
ans = min(ans, res);
}
printf("%lld
", ans);
}
return 0;
}集計ソート:46 ms(こんなに効率的だとは思わなかったので、マスター)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 5000+10
#define LL long long
using namespace std;
int a[MAX], tmp[MAX];
int b[MAX];//
LL ans;
void Merge(int l, int m, int r)
{
int i = l;
int j = m + 1;
int k = l;
while(i <= m && j <= r)
{
if(a[i] > a[j])
{
tmp[k++] = a[j++];
ans += m - i + 1;
}
else
{
tmp[k++] = a[i++];
}
}
while(i <= m) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(int i = l; i <= r; i++)
{
a[i] = tmp[i];
}
}
void Merge_sort(int l,int r)
{
if(l < r)
{
int m = (l + r) >> 1;
Merge_sort(l,m);
Merge_sort(m+1,r);
Merge(l,m,r);
}
}
int main()
{
int n;
int i, j;
LL res;
while(~scanf("%d", &n))
{
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
ans = 0;
Merge_sort(0,n-1);
res = ans;
for(i = 0; i < n; i++)
{
res += n - 1 - b[i] - b[i];
ans = min(ans, res);
}
printf("%lld
", ans);
}
return 0;
}