P14981 [USACO26JAN1] Milk Buckets G 题解

思路

注意到每次合并相当于将合并的两个数对答案的贡献 $\times\frac{1}{2}$，所以合并顺序一定是从小到大。

注意到当序列为单谷序列时符合合并条件，问题转化为将序列变为单谷的最小操作次数。

注意到对于一个数，要么将他移到序列谷的左侧，要么移到右侧，移动的代价即为两侧比它小的数的数量中的较小值。

所以只需要离散化后用树状数组统计一下就好了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,a[200010],lsh[200010],L[200010],R[200010],ln;
int lowbit(int x){
	return x&(-x);
}
struct TR{
	ll tr[200010];
	void add(int x,int v){
		for(int i=x;i<=ln;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	ll find(int x){
		ll ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			lsh[i]=a[i];
		}
		sort(lsh+1,lsh+1+n);
		ln=unique(lsh+1,lsh+1+n)-lsh-1;
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
		}
		for(int i=1;i<=ln;i++)tr.tr[i]=0;
		for(int i=1;i<=n;i++){
			L[i]=tr.find(a[i]-1);
			tr.add(a[i],1);
		}
		for(int i=1;i<=ln;i++)tr.tr[i]=0;
		for(int i=n;i;i--){
			R[i]=tr.find(a[i]-1);
			tr.add(a[i],1);
		}
		ll ans=0;;
		for(int i=1;i<=n;i++)ans+=min(L[i],R[i]);
		cout<<ans<<'\n';
	}
	return 0;
}

先考虑如何让最终权值最大。将合并视作两个桶的贡献系数乘以 $\frac 12$，则最终答案可以理解成 $\sum a_ic_i$，其中 $\sum c_i=1$，且 $c_i$ 形如 $\frac 1{2^l}$。尝试将 $c_i$ 乘以 $2$，则其他 $c$ 一共需要有恰好 $c_i$ 的减量。此时，若产生减量对应的 $a$ 均小于 $a_i$，最终答案一定不降。于是可以发现按 $a_i$ 从大到小将 $c_i$ 赋值为 $\frac 12,\frac 14,\frac 18,\ldots$ 可以得到最优解。

这样的 $c$ 如何体现在合并中？不难发现就是从最小值逐渐与更大的值合并，这要求前 $x$ 小放在一起，也即最终的 $a$ 是单谷的。

现在变成了另一个问题，如何用最少交换次数让 $a$ 变成单谷的。从谷两端入手，从大到小遍历 $a$ 中的相同值，找到其下标分别为 $p_1<p_2<\cdots<p_m$，此时需要找到一个分界点 $q$，使得 $q$ 左边移动到最左端，右边移动到最右端的总操作数，即 $\displaystyle\sum_{i=1}^q p_i-i+\sum_{i=c+1}^mn-p_i-(m-i)$（假设当前左右端仍为 $1,n$）最小，这两个求和可以前缀和完成。可以通过树状数组维护当前相对下标来找到 $p$。

最终时间复杂度 $\mathcal{O}(n\log n)$。

:::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=200007,ee=1e18,p=998244353;
ll n,a[maxn],ans,id[maxn],s1[maxn],s2[maxn];
struct Tree{
    ll val[maxn];
    void init(ll n){fill(val+1,val+1+n,0);}
    void add(ll x,ll k){for(;x<=n;x+=x&(-x)) val[x]+=k;}
    ll ask(ll x){ll E=0; for(;x;x-=x&(-x)) E+=val[x]; return E;}
}tree;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n,ans=0;
        for(ll i=1;i<=n;i++) cin>>a[i],id[i]=i;
        sort(id+1,id+1+n,[&](ll x,ll y){
            if(a[x]!=a[y]) return a[x]>a[y];
            else return x<y;
        });
        tree.init(n);
        for(ll i=1;i<=n;i++) tree.add(i,1);
        for(ll l=1,r,x,mx;l<=n;l=r+1){
            for(r=l;r<=n&&a[id[l]]==a[id[r]];r++);
            r--,s1[l-1]=s2[l-1]=0;
            for(ll i=l;i<=r;i++){
                x=tree.ask(id[i]);
                s1[i]=s1[i-1]+x-(i-l+1);
                s2[i]=s2[i-1]+(n-l+1)-x-(r-i);
            }
            mx=s2[r];
            for(ll i=l;i<=r;i++){
                mx=min(mx,s1[i]+s2[r]-s2[i]);
                tree.add(id[i],-1);
            }
            ans+=mx;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

:::