题解：P14419 [JOISC 2014] 有趣的家庭菜园 / Growing Vegetables is Fun

模拟赛 T4，被 T2 创飞根本没看倒闭倒闭倒闭倒闭，爽爽爽爽爽。

首先我们注意到最后的序列一定是呈一个单峰的样子。

然后发现对于需要单增的序列的交换次数为其逆序对数，单减序列相当于顺序对数。

然后我们考虑对于一个数

i

，是将其放在单增序列还是单减序列中，加上其顺、逆序对数即可。

使用树状数组维护，时间复杂度

O(n\log n)

。

CPP

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_Start;
constexpr int N=3*1e5+10;
int _=1,n,ans=0,cnt1=0,cnt2=0,a[N],p[N],q[N],c[N][2];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
}inline void clr(){
//	Don't Forget!

}int lowbit(int x){return x&(-x);}
void add(int x,int d,int opt){for(int i=x;i<N;i+=lowbit(i)) c[i][opt]+=d;}
int asks(int x,int opt){
	int cnt=0;
	for(int i=x;i>=1;i-=lowbit(i)) cnt+=c[i][opt];
	return cnt;
}
bool Test_MLE_End;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_End-&Test_MLE_Start-1)/1024.0/1024.0);
	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) p[i]=a[i]=reads();
		sort(p+1,p+n+1);int cnt=unique(p+1,p+n+1)-p-1;
		for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
		memset(p,0,sizeof(p));
		for(int i=n;i>=1;i--){
			p[i]=asks(n,1)-asks(a[i],1);
			add(a[i],1,1);
		}for(int i=1;i<=n;i++){
			q[i]=asks(n,0)-asks(a[i],0);
			add(a[i],1,0);ans=ans+min(q[i],p[i]);
		}printf("%lld\n",ans);
	}return 0;
}

题解：P14419 [JOISC 2014] 有趣的家庭菜园 / Growing Vegetables is Fun

文章操作

相关推荐

评论

题解：P14419 [JOISC 2014] 有趣的家庭菜园 / Growing Vegetables is Fun