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

ltz761222 · 2025-11-23 15:03:19 · 题解

题目描述

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

思路

首先有暴力 DFS 的思路。

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

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

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

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

代码

::::info[不要抄我]

#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;
}

::::