UOJ49 【UR #3】铀仓库题解

题意：

顽皮的 cxy 潜入了著名核物理专家 Picks 的研究所，走进了存放浓缩铀的仓库。

浓缩铀存放在一个个箱子里，一共有 $n$ 叠箱子排成一条直线，不妨想象一根数轴，第 $i$ 叠箱子坐标为 $x_i$，竖直方向叠着 $a_i$ 个箱子。

cxy 脑洞大开，决定进行一项游戏。她会先选择一个整数坐标 $s$（可以不和任意一个 $x_i$ 相等），然后初始时她两手空空站在坐标 $s$ 处，进行至多 $t$ 秒的行动。

这段时间内她的行动方式包括：

向左移动单位 $1$ 的距离，花费 $1$ 秒。

向右移动单位 $1$ 的距离，花费 $1$ 秒。

如果现在手上是空的，那么可以从当前位置拿起一个装有浓缩铀的箱子，瞬间完成。

如果现在拿着一个装有浓缩铀的箱子，那么可以把这个箱子放在当前位置所有箱子的顶部，瞬间完成。

~~由于 cxy 很小~~，任意时刻她只能拿着至多一个箱子。她希望进行至多 $t$ 秒的行动后，初始位置 $s$ 叠着的箱子尽量多。

请你帮 cxy 计算，她如果 $s$ 选择得恰到好处，并且行动足够机智，那么最多能在位置 $s$ 叠放多少个箱子。

输入格式：

第一行两个整数 $n, t$。保证 $n \geq 1, t \geq 0$。

第二行 $n$ 个严格递增的正整数，第 $i$ 个为 $x_i$。

第三行 $n$ 个正整数，第 $i$ 个为 $a_i$。

输出格式：

一行一个非负整数，表示位置 $s$ 至多能叠放多少个箱子。

数据范围：

对于全部数据，均有 $1 \le a_i \le 10^4$，$1 \le x_i \le 10^9$，且输入时 $x_i$ 严格递增。

结论1：当 $s$ 固定时，一定是先确定一个目标箱子，然后她跑过去再回来，单次花费 $2|s-x_i|$ 。

证明：显然，如果不搬到 $s$ 则不会产生贡献，要产生贡献只能搬到 $s$ 。$\square$

根据贪心常识，一定会让她优先跑到最近的箱子。

以上结论还是比较好想的，接下来这个就比较难发现了

结论2：如果她要搬的箱子集合是固定的，那对于相邻两个位置 $i,~i+1$ 和任意的 $x_i \le x \le x_{i+1}$

记 $f(x)$ 为给定箱子数量且初始位置 $s = x$ 时的最小耗时，则 $f(x)$ 是关于 $x$ 的一次函数。

证明：记箱子集合为 $S=U\cup V$ （在 $x_i$ 及左边的部分为 $U$ ，在 $x_{i+1}$ 及右边的部分为 $V$ ），则

$\begin{aligned} f(x) &= \sum_{i \in S}2|x-x_i| \\[6pt]&= \sum_{i \in U}2(x-y_i) + \sum_{i \in V}2(x_i - x) \\[6pt]&= 2x(|U| - |V|) + 2\left(\sum_{i \in V} x_i - \sum_{i \in U}x_i\right) \\[6pt]&= Ax + B \end{aligned}$

容易发现 $f(x)$ 为一次函数，则极值在端点处取到。$\square$

故我们只需要考虑初始位置 $s$ 等于某个 $x_i$ 的情况即可。

注意到「给定时间内最多取几个箱子」并不好计算，因此我们可以计算「给定箱子求最少时间」。

显然答案存在单调性，所以我们二分箱子的个数 $v$ 。

考虑枚举 $s$ ，再用双指针维护需要搬的箱子集合，因为随着 $s$ 递增，“优先区间”也会右移

并维护前缀和 $\mathtt{s_1},\mathtt{s_2}$ 分别记录 $\sum a_i$ 和 $\sum a_ix_i$ 的值，然后套上面的公式计算，即

$\sum_{l<i<s} a_i (x_s - x_i) + \sum_{s<i<r} a_i (x_i - x_s) + \mathtt{lc} \times(x_s - x_l) + \mathtt{rc} \times (x_r - x_s)$

其中 $\mathtt{lc},\mathtt{rc}$ 均为「端点处」取的箱子数，显然其中一定有一个为 $0$ 。

时间复杂度 $\mathcal{O}(n \log^2 n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5+15))

int n,t,x[N],a[N],s1[N],s2[N];
bool work(int v)
{
    int l = 1, r = lower_bound(s1+1, s1+1+n, v) - s1;
    int lc = a[1], rc = v - s1[r-1], res;
    for(int s=1,xs; s<=n; s++)
    {
        xs = x[s];
        for(int d; l<s && r<=n && xs*2 > x[l] + x[r]; )
        {
            d = min(lc, a[r] - rc);
            if((lc -= d) == 0) lc = a[++l];
            if((rc += d) == a[r]) ++r, rc = 0;
        }
        res = xs * (s1[s] * 2 - s1[l] - s1[r-1] + lc - rc)
            + s2[l] + s2[r-1] - s2[s]*2 - lc * x[l] + rc * x[r];
        if(res <= t) return 1;
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> t; t >>= 1;
    for(int i=1; i<=n; i++) cin >> x[i];
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        s1[i] = s1[i-1] + a[i];
        s2[i] = s2[i-1] + a[i] * x[i];
    }
    int l = 0, r = s1[n];
    while(l < r)
    {
        int mid = (l+r+1) >> 1;
        work(mid) ? (l=mid) : (r=mid-1);
    }
    cout << l << '\n';
    return 0;
}