Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 4240 有趣的家庭菜园

对家庭菜园有兴趣的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草的不会枯萎的最少操作次数。


题意:找一个数列,使该数列中从该元素开始,从左往右递降,从右往左递降(找个山峰),使所给的数列与原数列冒泡交换的次数最小。

一开始想错了,想的是L[i]表示1~i形成从小到大的数列交换次数最小,R[i]表示从i~n形成从大到小的交换次数最小。设f(x)=L[x]+R[x+1],然后答案就是min{f(i)}。
后来发现其实最优情况可能有左边跑到右边去,但无法通过x取值的改变而枚举到该情况。。= =感觉药丸

答案是按照键值从小到大排序,然后从小的开始处理。因为每次处理的都是未处理的最小的,所以肯定在最左边或者最右边,用树状数组维护一下当前元素从当前位置调整到最左边或者最右边哪一种情况代价小,然后删除该数的标记。

值得注意的是,当遇到两个数相同,这两个数的相对位置是不用改变的,所以每次要减去与相同元素交换的代价。

code

#include<bits/stdc++.h>
#define ll long long
const int N =3e5+3e3;
int read(){
    int x=0,fl=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')fl*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*fl;
}
int n;
ll L[N],R[N],sum[N];
struct A {
    int v,pos;
    bool operator < (const A m) const{
        return v<m.v;
    } 
}a[N];
void add(int a,int x){
    for(;a<=n;a+=a&(-a)) sum[a]+=x;
}
ll ask(int a){
    ll ans=0;for(;a;a-=a&(-a)) ans+=sum[a];
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i)
        a[i].v=read(),a[i].pos=i,add(a[i].pos,1);
    std::sort(a+1,a+1+n);
    int sum=n;ll ans=0;
    for(int i=1,j=i;i<=n;i=j){
        j=i;
        while(a[j].v==a[i].v&&j<=n) add(a[j].pos,-1),++j,sum--;
        j=i;
        while(a[j].v==a[i].v&&j<=n)
             ans+=std::min(sum-ask(a[j].pos),ask(a[j].pos)),++j;
    }
    printf("%lld\n",ans);
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/336
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      线段树      BZOJ 4240 有趣的家庭菜园
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ 4240 有趣的家庭菜园
对家庭菜园有兴趣的JOI君每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为N个区域,由西到东标号为1~N。IOI草一共有N株,每个区域种植着一株。在第i个区域种植…
扫描二维码继续阅读
2018-09-13