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

题目描述

每次可以交换序列相邻的两个位置，使用最少操作使得序列呈现单峰，序列中的数可以重复。

思路

首先有暴力 DFS 的思路。

这个思路可以优化。考虑到最小的节点一定在最左或者最右的位置，可以顺次枚举在左还是在右。

注意到一个节点向左和向右需要越过一些比他大的节点，这个个数是确定的，只需要知道有多少步不改变这个数就可以贪心。

然后这个题最难受的地方就来了：没有。

具体证明是首先如果两个点值相同一定不会交换，其次如果每个数在要走的方向上，相邻的那个点比我小，那么讨论一下方向，易证如果没有任何一种操作可以减少这个数，此时已经合法。

代码

不要抄我

CPP

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=3e5+9;
struct sandness{
	int w,x;
}sandy[N];int hp[N],tot;
int A[N],S[N],C[N],tr[N];
int n;ll ans;

/**/

inline int  read();
inline void init();

#define lowbit(i) (i&-i)
inline void update(int w,int x);
inline int  query(int w);

int main()
{
//	freopen("swap.in","r",stdin);
//	freopen("swap.out","w",stdout);
//	freopen("swap2.in","r",stdin);
//	freopen("swap2.out","w",stdout);
	
	scanf ("%d",&n);
	for (int i=1;i<=n;i++)
		A[i]=read();
	init();
	
	for (int i=1;i<=tot;i++)
		tr[i]=0;
	for (int i=1;i<=n;i++)
		S[i]=query(A[i]-1),update(A[i],1);
	for (int i=1;i<=tot;i++)
		tr[i]=0;
	for (int i=n;i>=1;i--)
		C[i]=query(A[i]-1),update(A[i],1);
	
	for (int i=1;i<=n;i++)
		ans+=min(S[i],C[i]);
	printf ("%lld\n",ans);
	
	return 0;
}

inline int  read()
{
	int o=0,c=0,g=0;
	while (c<'0' or c>'9')
		g=(c=='-'),c=getchar();
	while (c>='0' and c<='9')
		o=(o<<1)+(o<<3)+(c^48),c=getchar();
	return (!g)?o:-o;
}

inline void init()
{
	for (int i=1;i<=n;i++)
		sandy[i]={i,A[i]};
	stable_sort(sandy+1,sandy+n+1,[&](sandness u,sandness v){
		return u.x>v.x;
	});
	
	for (int i=1;i<=n;i++)
		tot+=(i==1 or sandy[i].x!=sandy[i-1].x),hp[tot]=sandy[i].x,A[sandy[i].w]=tot;
}

inline void update(int w,int x)
{
	for (int i=w;i<=tot;i+=lowbit(i))
		tr[i]+=x;
}

inline int  query(int w)
{
	int res=0;
	for (int i=w;i>=1;i-=lowbit(i))
		res+=tr[i];
	return res;
}

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

文章操作

题目描述

思路

代码

相关推荐

评论

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