【UOJ#49】【UR#3】铀仓库 | Mrsrz's blog

二分答案，双指针

题目大意：

有 $n$ 个位置，第 $i$ 个位置在坐标 $x_i$，有 $a_i$ 个箱子。

你在坐标 $k$ 的时候可以干几件事：

1. 花费 $1$ 秒使自己坐标变为 $k-1$。
2. 花费 $1$ 秒使自己坐标变为 $k+1$。
3. 若手中没箱子，坐标 $k$ 有，则可以瞬间拿起一个箱子。同时只能拿一个。
4. 若手中有箱子，坐标 $k$ 没有，则可以瞬间把箱子放到坐标 $k$ 上。

给你 $t$ 秒，要求选定一个初始坐标 $s$，并花费不超过 $t$ 秒的时间，使得坐标 $s$ 处的箱子最多。

问最多是多少。

题解：

几个结论：

1. 对于一个箱子，从起点直奔它而去然后回来是最优的。因为每次只能搬一个箱子，所以箱子是互相独立的，不难证明直接搬最优，其它最优搬法和直接搬是等价的。
2. 存在一个最优答案，它的 $s$ 处本身就有箱子。若 $s$ 处无箱子，则我们可以将它向箱子选得多的方向移动到有箱子的坐标，使答案变优，若两边箱子取的个数相同，则移动没有影响。
3. 每次取离 $s$ 最近的箱子最优。显然。

考虑二分答案 $m$，那么相当于求取 $m$ 个箱子要花费的最少时间。

我们枚举起点 $s$ 的位置，维护每个起点的最优值，用双指针维护它取的最左、最右的箱子的位置。$s=x_1$ 时的答案可以 $O(n)$ 求出。

当 $s$ 变化的时候，我们可以 $O(1)$ 计算答案的变化量。然后考虑贪心，尝试用右边的箱子替换掉左边的箱子，更新答案。时间复杂度 $O(n)$。

因此总时间复杂度 $O(n\log(\sum a)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e5+5;
typedef long long LL;
int n,pos[N],a[N],in[N];
LL sm,t;
bool check(LL k){
    for(int i=1;i<=n;++i)in[i]=0;
    int l=1,r=1;LL sL=a[1],sR=0;
    in[1]=a[1];
    LL tm=0;
    while(r<=n&&sL+sR<k){
        if(in[r]==a[r])++r;
        if(r>n)break;
        LL DT=k-sL-sR;
        if(a[r]-in[r]>DT){
            sR+=DT;
            tm+=(LL)(pos[r]-pos[1])*DT;
            in[r]+=DT;
        }else{
            DT=a[r]-in[r];
            sR+=DT;
            tm+=(LL)(pos[r]-pos[1])*DT;
            in[r]+=DT;
        }
    }
    if(sL+sR<k)return 0;
    if(tm<=t)return 1;
    for(int i=2;i<=n;++i){
        tm+=(LL)(pos[i]-pos[i-1])*(sL-sR);
        while(r<=n){
            while(!in[l])++l;
            while(a[r]==in[r])++r;
            if(r>n||pos[i]-pos[l]<pos[r]-pos[i])break;
            int dt=min(in[l],a[r]-in[r]);
            tm-=(LL)(pos[i]-pos[l])*dt;tm+=(LL)(pos[r]-pos[i])*dt;
            in[l]-=dt,in[r]+=dt;
            sL-=dt,sR+=dt;
        }
        if(tm<=t)return 1;
        sR-=in[i],sL+=in[i];
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>t,t/=2;
    for(int i=1;i<=n;++i)cin>>pos[i];
    for(int i=1;i<=n;++i)cin>>a[i],sm+=a[i];
    LL l=*max_element(a+1,a+n+1)+1,r=sm,ans=l-1;
    while(l<=r){
        const LL mid=(l+r)/2;
        if(check(mid))l=(ans=mid)+1;else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}