[NOIp2013] luogu P1966 火柴排队

磕了瓶魔爪。

题目描述

你有两个长度为 NNN 的数组 a,ba,ba,b，试重新排列 aaa 数组使得S=∑i=1n(ai−bi)2S=\sum_{i=1}^{n}{(a_i-b_i)^2}S=i=1∑n(ai−bi)2的值最小。你可且仅可以交换相邻的两个数。求最小交换数对 99,999,99799,999,99799,999,997 取模的值。

Solution

容易得到(∑i=1nai)2+(∑i=1nbi)2=S−2∑i=1naibi(\sum_{i=1}^{n}{a_i})^2+(\sum_{i=1}^{n}{b_i})^2=S-2\sum_{i=1}^{n}{a_ib_i}(i=1∑nai)2+(i=1∑nbi)2=S−2i=1∑naibi

显然前几项都是定值，我们只能在最后一项中做文章。

注意到，将 a,ba,ba,b 数组排序后，aia_iai 与 bib_ibi 配对一定最优（反证法证明）。于是先离散化，然后排序，树状数组求逆序对个数即可。时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

const int MAXN=100010;

const int MOD=99999997;

int n;

struct node{

	int d,id;

	friend bool operator<(const node a,const node b){

		return a.d<b.d;

	}

}a[MAXN],b[MAXN];

int c[MAXN];

int bk[MAXN];

void Sort(){

	//此处写的较为繁琐，但是可读性强

	std::sort(a+1,a+n+1);

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

		c[a[i].id]=i;

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

		a[i].id=c[i];

	std::sort(b+1,b+n+1);

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

		c[b[i].id]=i;

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

		b[i].id=c[i];

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

		c[a[i].id]=i;

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

		a[i].id=c[b[i].id];

}

int tree[MAXN];

int lowbit(int x){

	return x&(-x);

}

void change(int x,int y){

	while(x<=n){

		tree[x]+=y;

		x+=lowbit(x);

	}

}

int que(int x){

	int cnt=0;

	while(x){

		cnt+=tree[x];

		x-=lowbit(x);

	}

	return cnt;

}

int query(int l,int r){

	return que(r)-que(l-1);

}

//求逆序对个数

void Calc(){

	memset(tree,0,sizeof(tree));

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

		bk[a[i].id]=i;

	int cnt=0;

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

		change(bk[i],1);

		cnt=(cnt+query(bk[i]+1,n))%MOD;

	}

	printf("%d",cnt);

}

inline int read(){

	int x=0; char c;

	do c=getchar(); while(c<'0'||c>'9');

	while(c>='0'&&c<='9')

		x=x*10+c-48,c=getchar();

	return x;

}

int main(){

	n=read();

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

		a[i].d=read();

		a[i].id=i;

	}

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

		b[i].d=read();

		b[i].id=i;

	}

	Sort();

	Calc();

}

巴特西

[NOIp2013] luogu P1966 火柴排队

题目描述

Solution

最新文章

热门文章