【NOIP13 D1T2】火柴排队

Source and Judge

NOIP2013 提高组 D1T2
Luogu1966
Caioj1558

Problem

【Description】
两个长为 n 的序列 a,b ,定义两个序列的距离为:sigma (ai-bi)^2
每个序列中相邻两个位置的数可以交换,问最少需要交换多少次,可以最小化这个柿子?
最小交换次数对 99,999,997 取模。
【Input】
共三行,第一行包含一个整数 n。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列数。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列数。
【Output】
输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。
【Limited conditions】
对于 10%的数据, 1 ≤ n ≤ 10;
对于 30%的数据,1 ≤ n ≤ 100;
对于 60%的数据,1 ≤ n ≤ 1,000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤ maxint
【Sample input】
4
1 3 4 2
1 7 2 4
【Sample output】
2
【Sample explanation】
最小距离是 10,最少需要交换 2 次,
比如:交换第 1 列的中间 2 根火柴的位置,再交换第 2 列中后 2 根火柴的位置。

Record

30min

Analysis

请先思考后再展开

显然为了让两列差值最小,让【两边同一排名的在一行】显然是最优的
(可以自己推推柿子,其他调整不会更优)
那么既然只关心排名,先离散化一波

然后两边保证不同,是两个排列,现在要对齐
将右边变成1、2、3……左边对应修改
然后就相当于对左边排序,逆序对即可

Code

请先思考后再展开
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-') f=-1;;c=getchar();}
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
int n;
const int MAX_N=110000;
int bit[MAX_N];
int lowbit(int x){return x&-x;}
void change(int x,int c)
{
while(x<=n)
{
bit[x]+=c;
x+=lowbit(x);
}
}
int ask(int x)
{
int ans=0;
while(x>0) ans+=bit[x],x-=lowbit(x);
return ans;
}
struct Nod{int d,p;}p[MAX_N],p2[MAX_N];
bool cmp(Nod a,Nod b) {return a.d<b.d;}
int a[MAX_N],b[MAX_N];
void main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i].d),p[i].p=i;
sort(p+1,p+n+1,cmp);
int now=1;a[p[1].p]=now;
for(int i=2;i<=n;i++)
{
if(p[i-1].d!=p[i].d) now++;
a[p[i].p]=now;
}
memcpy(p2,p,sizeof p);//backup
for(int i=1;i<=n;i++) scanf("%d",&p[i].d),p[i].p=i;
sort(p+1,p+n+1,cmp);
now=1;b[p[1].p]=now;
for(int i=2;i<=n;i++)
{
if(p[i-1].d!=p[i].d) now++;
b[p[i].p]=now;
}
for(int i=1;i<=n;i++)
{
int to=lower_bound(p2+1,p2+n+1,(Nod){b[i],0},cmp )-p2;
a[ p2[to].p ]=i;
}
for(int i=1;i<=n;i++) if(LOCAL) printf("a[%d]=%d\n",i,a[i]);
int ans=0;
for(int i=1;i<=n;i++)
{
int all=i-1,sm=ask(a[i]);
ans=(ans+all-sm)%99999997;
change(a[i],1);
}
printf("%d\n",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/421b.html
转载请注明出处,谢谢!