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;
}