首页 > 代码库 > 【BZOJ4240】有趣的家庭菜园 树状数组+贪心

【BZOJ4240】有趣的家庭菜园 树状数组+贪心

2024-10-17 12:45:02   215人阅读

【BZOJ4240】有趣的家庭菜园

Description

对家庭菜园有兴趣的JOI君每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为N个区域，由西到东标号为1~N。IOI草一共有N株，每个区域种植着一株。在第i个区域种植的IOI草，在春天的时候高度会生长至hi，此后便不再生长。
为了观察春天的样子而出行的JOI君注意到了IOI草的配置与预定的不太一样。IOI草是一种非常依靠阳光的植物，如果某个区域的IOI草的东侧和西侧都有比它高的IOI草存在，那么这株IOI草就会在夏天之前枯萎。换句话说，为了不让任何一株IOI草枯萎，需要满足以下条件：
对于任意2<=i<=N-1，以下两个条件至少满足一个：
1. 对于任意1<=j<=i-1，hj<=hi
2. 对于任意i+1<=j<=N，hk<=hi
IOI草是非常昂贵的，为了不让IOI草枯萎，JOI君需要调换IOI草的顺序。IOI草非常非常的高大且纤细的植物，因此JOI君每次只能交换相邻两株IOI草。也就是说，JOI君每次需要选择一个整数i(1<=i<=N-1)，然后交换第i株IOI草和第i+1株IOI草。随着夏天临近，IOI草枯萎的可能性越来越大，因此JOI君想知道让所有IOI草都不会枯萎的最少操作次数。
现在给出田地的区域数，以及每株IOI草的高度，请你求出让所有IOI草的不会枯萎的最少操作次数。

Input

第一行一个正整数N，代表田地被分为了N个区域。
接下来N行，第i行(1<=i<=N)一个整数hi，表示第i株植物在春天时的高度

Output

输出一行一个整数，表示最少需要的操作次数

Sample Input

6
2
8
4
5
3
6

Sample Output

3

HINT

最终的高度序列为2 4 5 8 6 3，共需要操作三次。
3<=N<=3*10^5
1<=hi<=10^9

题解：一个经常用到的结论：我们给原数组标上下表1...n，移动若干次后我们会得到一个新的下标序列，需要的搬运次数就是这个新序列的逆序对数。

所以我们思考怎样让新序列的逆序对数更少就行了。题中要求最终序列满足h值先递增再递减，所以最大的一定放到中间，次大的可以放在最大的两边，再次的放在前两大的两边。。。所以，当放入第k大的时候，我们贪心选择可以形成较少的逆序对的那边放，并且这样做不会影响到后面的节点。

还有如果多个草高度相同要特判一下。

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn=300010;typedef long long ll;ll ans;int n,l,r;int s[maxn],v[maxn],p[maxn];void updata(int x,int val){	for(int i=x;i<=n;i+=i&-i)	s[i]+=val;}int query(int x){	int i,ret=0;	for(i=x;i;i-=i&-i)	ret+=s[i];	return ret;}bool cmp(int a,int b){	return v[a]>v[b];}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	scanf("%d",&n);	int i,j,a;	for(i=1;i<=n;i++)	v[i]=rd(),p[i]=i;	sort(p+1,p+n+1,cmp);	for(i=1;i<=n;)	{		for(j=i;j<=n;j++)		{			a=query(p[j]),ans+=min(a,i-1-a);			if(v[p[j+1]]!=v[p[j]])	break;		}		for(;i<=j;i++)	updata(p[i],1);	}	printf("%lld",ans);	return 0;}

 

【BZOJ4240】有趣的家庭菜园 树状数组+贪心


联系
我们