BOXES 题解

Transparent · 2023-05-25 22:08:17 · 题解

提供一种比费用流更优秀的 dp 做法，但是不能通过 Hard Version。

这个做法可以解决：给定一个环和环上每个位置初始的元素个数 a_i，求最小的移动次数使得每个位置剩下的元素在 [l_i,r_i] 中。显然本题中，对任意的 i 都有 l_i=0,r_i=1

考虑断开一条边成为链的情况，通过枚举断开的边的传递情况就可以解决环的问题。这时第一个位置只能向后传递。于是可以 dp，设 dp_{i,j} 表示前 i 个位置已经合法且第 i 个位置往下一个位置传递了 j 个时（j 为负数表示从下一个位置拿到 i），传递次数的最小值。于是可以得出转移方程：

dp_{i,j}=\min\limits_{k=j-a_i+l_i}^{j-a_i+r_i}\{dp_{i-1,k}\}+|j|

显然可以单调队列做到 \Theta(n\sum\limits_{i=1}^{n} a_i)。

复杂度还不优秀，考虑优化转移的过程。令 f_i(x)=dp_{i,x}。发现每次从 dp_i 到 dp_{i+1} 其实可以拆分成三个操作：

令 f(x)=\min\limits_{i=x}^{x+a}f(i)
令 f(x) 沿 x 轴方向左右平移 a 个单位。
令 f(x)=f(x)+|x|

首先发现，在 i=0 的时候，只有 f_0(0)=0，f_0(x) 的其余地方均为 +\infty。这显然是下凸的。而 |x| 同样是下凸的，并且对一个凸函数进行前两个操作后得到的显然还是凸函数，于是可以将问题转化为维护一个下凸包。

考虑用对顶堆实现，两个堆存放斜率的转折点，其中一个维护斜率大于 0 的部分，另一个维护小于 0 的部分。堆中的每个元素表示斜率在对应的 x 处增减 1，而重复的元素则可以表示大于 1 的斜率变化，同时维护一个最小值。然后分别实现这三个操作：

第一个操作即为：在斜率为 0 的位置分开，将上升段向右平移 a 个单位，直接对上升段打 tag 即可，对最值无影响。

第二个操作直接对上升段和下降段一起打 tag 即可，对最值无影响。

第三个操作中，由于 x=0 处函数增减性可能不同，需要分类讨论：

（即下降段最后一个转折点）会在修改后不再属于下降段，因为现在在这个点，斜率是由 $0$ 变为 $1$，需要从下降段移除并加入上升段，显然，最值需要加上下降段末尾到 $0$ 的距离。

最后根据最低点的值，沿斜率转折点依次移到 x 即可。

至此，一次 dp 的复杂度可以做到 O(n\log_2n)。

现在还需要确定断开的那条边上的传递情况，如果枚举，就可以得到一个 O(n\log_2n\sum\limits_{i=1}^{n}a_i) 的做法。但是还可以优化。

设 F(x) 表示 n 给 1 拿 x 个时，需要的最小操作次数。打表发现好像是凸函数，考虑证明。

首先，将每次移动次数拓展到实数，答案不变。感性理解是要取得最值时，一定有至少一个位置恰为 l_i 或 r_i，否则不传递这些小数部分不会更劣。当然，费用流做法也可以证明这个结论，因为把费用流做法拓展到实数显然结果不变。

然后假设有两个合法方案 (a_1,a_2,\dotsb,a_n) 和 (b_1,b_2,\dotsb,b_n)，其中第 i 个数表示第 i 个位置向下一个位置传递的次数。此时将两个方案的每个位置求平均值，得到新的方案 (c_i) 使得 c_i=\frac{a_i+b_i}{2}。由于前两个方案都合法，所以它们都能使得每个位置的值在 [l_i,r_i] 内，于是它们求平均值后显然也都能落在区间内。因为有 |c_i| \le |\frac{a_i+b_i}{2}|\le |\frac{a_i}{2}|+|\frac{b_i}{2}|，所以 \sum\limits_{i=1}^{n}|c_i| \le \sum\limits_{i=1}^{n}|\frac{a_i}{2}|+|\frac{b_i}{2}|，令 F(A)=\sum\limits_{i=1}^{n}|a_i|，F(B),F(C) 同理。根据定义得到 C=\frac{A+B}{2}，又有 F(C) \le \frac{F(A)+F(B)}{2} 即 F(\frac{A+B}{2}) \le \frac{F(A)+F(B)}{2} 于是 F(x) 是凸函数。

于是可以在最外层套三分，最终复杂度为 O(n\log_2n\log_2\sum\limits_{i=1}^{n}a_i)。

#include <ext/pb_ds/priority_queue.hpp>
#include<bits/stdc++.h>

using namespace std;

constexpr int MAXN=2e5+10;

int n,a[MAXN];

int calc(int x) {
    int tagl=0,tagr=0,val=0;
    __gnu_pbds::priority_queue<int,less<int>,__gnu_pbds::pairing_heap_tag>ql;
    __gnu_pbds::priority_queue<int,greater<int>,__gnu_pbds::pairing_heap_tag>qr;
    for(int i=1;i<=n;++i) ql.push(x),qr.push(x);

    for(int i=1;i<=n;++i) {
        tagl+=a[i]-1;tagr+=a[i];
        int lp=ql.top()+tagl,rp=qr.top()+tagr;
        if(lp<=0&&0<=rp) {
            ql.push(-tagl);qr.push(-tagr);
        } else if(lp>0) {
            val+=lp;ql.pop();ql.push(-tagl),ql.push(-tagl);qr.push(lp-tagr);
        } else {
            val-=rp;ql.push(rp-tagl);qr.pop();qr.push(-tagr);qr.push(-tagr);
        }
    }

    while(!ql.empty()) {
        int lp=ql.top()+tagl;ql.pop();
        if(lp<=x) break;
        val+=lp-x;
    }
    while(!qr.empty()) {
        int rp=qr.top()+tagr;qr.pop();
        if(rp>=x) break;
        val+=x-rp;
    }
    return val;
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];

    int suma=0;
    for(int i=1;i<=n;++i) suma+=a[i];

    int L=-suma,R=suma,res=0;
    while(L<=R) {
        int mid=(L+R)>>1;
        if(calc(mid)<calc(mid+1)) {
            res=mid,R=mid-1;
        } else L=mid+1;
    }

    cout<<calc(res)<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    int T=0;cin>>T;
    while(T--) solve();

    cout<<flush;
    return 0;
}