[USACO26JAN1] Milk Buckets G 题解

先不考虑最小的交换次数。题目中可以任意重排牛奶，相当于每次可以任意选择两桶牛奶合并。这启发我们先探索最优的合并策略，使得最后留下的一桶牛奶量最大。

在这里直接给出结论：每次选择量最少的两桶牛奶合并，这样的策略一定是最优的。

证明

将合并牛奶的过程抽象成一棵二叉树，叶子是初始的

a_1,a_2,\ldots,a_n

，每个内部结点表示一次合并：若它的两个子结点对应的牛奶量分别为

x,y

（单位：加仑；以下均默认单位为加仑），则它对应的量为

\frac{x+y}{2}

。根结点的量就是最终剩下那一桶牛奶的量。

进一步发现，如果规定根结点深度为

0

，一桶量为

a_i

的牛奶对最终答案的贡献必然形如

a_i\cdot 2^{-d_i}

，其中

d_i

为第

i

桶牛奶对应的叶子结点的深度（每合并一次，对最终的贡献就减半一次）。因为根结点对应的量为

\sum\limits_{i=1}^n a_i\cdot 2^{-d_i}

，所以需要让较大的 $a_i$ 匹配较小的 $d_i$ ，反之亦然。

不妨认为合并操作从深度大的结点先开始，那么第一次操作的两桶牛奶对应的叶子结点

d_i

是全局最大；根据上面的匹配策略，直接将这两个叶子对应量最小的两桶牛奶一定是最优的。道理也很简单，毕竟最后对根结点的贡献只看深度，具体怎么合并并不重要；反正这两桶牛奶都要在最深层，不妨直接认为它们具有相同的父结点（事实证明，这个策略其实会导致最深层仅有它们两个结点）。

将两桶量最小的牛奶合并后，就递归到了一个规模减少

1

的相同问题。归纳可得该策略最优。

接下来探索怎样的序列可以成功地执行这样的策略。每次合并两个最小的，也就是说对于

k=1,2,\ldots,n

，前

k

小的元素必须形成一个区间——换种说法，就是序列最终必须是单谷的（每次需要往区间左边 / 右边加入一个新元素，形成的序列自然是单谷的）。

现在问题变成了，执行最少次数的相邻交换操作，满足存在一个

k

，使得最终的序列形如

a_1\ge a_2\ge\cdots\ge a_k\le\cdots\le a_{n-1}\le a_n

。这是一个经典问题，在这里简单介绍一下做法：每次操作必然一个较大的元素和一个较小的元素进行交换，从大元素的视角来看，它最终要么到“谷底”的左边，要么到右边——如果它要到左边，那么代价即为“左边小于它的元素个数”，右边同理。这个值可以用树状数组维护，对于每个元素，根据两边算出来的答案，选择代价小的方向；最后将所有元素的代价求和即为总代价。

时间复杂度

O(n\log n)

。

放代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IAOI_lib{
  template<typename T> vector<T> discretization(vector<T> a){
    auto b=a; sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    for(auto &i:a)i=lower_bound(b.begin(),b.end(),i)-b.begin();
    return a;
  }
  template<typename T> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(int n):t(n){}
      int lowbit(int x){
        return x&-x;
      }
      void add(int p,T d){
        t[p++]+=d;
        while((p+=lowbit(p))<=t.size())t[p-1]+=d;
      }
      T pre_sum(int p){
        T s=t[p++];
        while((p-=lowbit(p))>0)s+=t[p-1];
        return s;
      }
      T sum(int l,int r){
        return l>r?0:pre_sum(r)-(l?pre_sum(l-1):0);
      }
  };
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n);
    for(auto &i:a)cin>>i;
    a=IAOI_lib::discretization(a);
    vector<int> f(n),g(n);
    IAOI_lib::fenwick_tree<int> t(n);
    for(int i=0;i<n;i++)
      t.add(a[i],1),f[i]=t.sum(0,a[i]-1);
    t=IAOI_lib::fenwick_tree<int>(n);
    for(int i=n-1;~i;i--)
      t.add(a[i],1),g[i]=t.sum(0,a[i]-1);
    // 预处理左右两边贡献
    ll c=0;
    for(int i=0;i<n;i++)
      c+=min(f[i],g[i]); // 对较小贡献求和
    cout<<c<<'\n';
  }
  return 0;
}

[USACO26JAN1] Milk Buckets G 题解

文章操作

相关推荐

评论

[USACO26JAN1] Milk Buckets G 题解