问题描述

在一条无穷长的数轴上摆放着 $n$ 个箱子。第 $i$ 个箱子在时刻 $0$ 位于 $a_i$ 处，目标是在时刻 $t_i$ 及之后的所有时刻位于 $b_i$ 处。移动规则如下：

• 每个单位时间，可以选择一个箱子向左或向右移动一个单位长度，但移动后的位置不能有其他箱子。

• 初始位置序列 $[a_1, \ldots, a_n]$ 和目标位置序列 $[b_1, \ldots, b_n]$ 均为单调递增。

需要判断是否存在一种移动方案满足所有箱子的要求。

算法思路

本题采用贪心策略结合并查集来管理箱子块的合并，通过排序和前缀和优化成本计算。核心思想是从截止时间最晚的箱子开始处理，逐步合并相邻的箱子块，并实时计算移动所需的最小步数。若当前所需步数超过箱子的截止时间，则判定为无解。

关键观察

1. 箱子块移动：由于移动时不能跨越其他箱子，连续的箱子可以形成一个块一起移动，从而减少总移动步数。

2. 成本计算：移动一个箱子块的成本可以通过前缀和快速计算。对于向右移动的块，成本为目标位置和与原始位置和的差；对于向左移动的块则相反。

3. 截止时间约束：截止时间最早的箱子必须最先满足，因此按截止时间从大到小处理，确保当前总步数不超过正在处理箱子的截止时间。

算法步骤

1. 预处理：

• 计算 $s[i] = a_i - i$，用于快速判断箱子是否连续（$s[i]$ 相等的箱子在数轴上连续）。

• 计算前缀和数组 sum[i]，其中 sum[i] = a[1] + a[2] + ... + a[i]。

• 初始化每个箱子的独立移动成本 val[i] = |a_i - b_i|，并求和得到当前总步数 now。

2. 排序：将箱子按截止时间 $t_i$ 从小到大排序，实际处理时从后往前（即从大到小）遍历。

3. 并查集初始化：每个箱子初始独立，使用并查集管理箱子块的合并。fa 数组用于记录每个位置所属的块的代表元。

4.贪心处理：

• 从截止时间最晚的箱子开始处理：

  • 检查当前总步数 now 是否大于当前箱子的截止时间 $t_i$。若是，则标记无解并退出。

  • 否则，将当前箱子与左右相邻的块合并。

  • 重新计算合并后块移动的成本（使用 cal 函数），并更新总步数 now。

• cal 函数根据移动方向（左或右）计算块移动成本：

  • 向右移动：找到连续块的最右端 $z$，成本为 $\text{val}[x] = (z-x+1) \times b_x + \frac{(z-x)(z-x+1)}{2} - (\text{sum}[z] - \text{sum}[x-1])$。

  • 向左移动：找到连续块的最左端 $z$，成本为 $\text{val}[x] = (\text{sum}[x] - \text{sum}[z-1]) - (x-z+1) \times b_x + \frac{(x-z)(x-z+1)}{2}$。

5. 输出结果：根据处理过程中的标记输出 "Yes" 或 "No"。

复杂度分析

• 排序：$O(n \log n)$。

• 并查集操作：近似 $O(n \alpha(n))$，其中 $\alpha(n)$ 为反阿克曼函数。

• 成本计算：每次使用二分查找，$O(\log n)$。

• 总复杂度：$O(n \log n)$，适用于 $n \leq 2 \times 10^5$。

算法标签

• 贪心：按截止时间从大到小处理，确保满足时间约束。

• 并查集：管理箱子块的合并与查询。

• 排序：对箱子按截止时间排序。

• 前缀和：快速计算移动成本。

• 二分查找：在成本计算中定位连续块的边界。

代码实现

#include <bits/stdc++.h>
using LL = long long;
using namespace std;
const LL N = 2e5 + 5;
LL t[N], s[N], val[N], fa[N << 1], sum[N];
pair<LL, LL> d[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
#ifdef ONLINE_JUDGE
//    freopen("move.in", "r", stdin);
//    freopen("move.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    int type, tc;
    cin >> type >> tc;

    for (int flag, n; tc-- and cin >> n;) {
        LL now = 0; // 记录当前所有未锁定箱子需要的总移动步数
        vector<int> a(n + 2), b(a);
        flag = 0;
        // cal函数: 计算一个箱子块[x, z]作为一个整体移动的成本
        auto cal = [&](LL x, LL y, LL op) {
            now -= val[x];  // 移除旧的、独立的成本

            if (!op) {      // op=0, 代表这是一个向右移动的块（以x为首）
                // 找到从x开始，物理上连续的箱子块的最右端z。s[i]=a[i]-i相等的箱子是连续的。
                LL z = lower_bound(s + x, s + y + 1, b[x] - x) - s - 1;
                // 计算将[x,z]移动到以b[x]为首的连续位置的成本
                val[x] = (z - x + 1) * b[x] + (z - x) * (z - x + 1) / 2 - sum[z] +
                         sum[x - 1],
                         now += val[x]; // 加上新块的成本
            } else { // op=1, 代表这是一个向左移动的块（以x为首）
                // 找到从x开始，物理上连续的箱子块的最左端z
                LL z = upper_bound(s + y, s + x + 1, b[x] - x) - s;
                // 计算将[z,x]移动到以b[x]-(x-z)为首的连续位置的成本
                val[x] = sum[x] - sum[z - 1] - (x - z + 1) * b[x] +
                         (x - z) * (x - z + 1) / 2,
                         now += val[x];
            }
        };

        for (LL i = 1; i <= n; i++)
            cin >> a[i] >> b[i] >> t[i],
                s[i] = a[i] - i,             // 预处理s[i]=a[i]-i，用于快速判断箱子是否连续
                       sum[i] = sum[i - 1] + a[i],  // a[i]的前缀和，用于快速计算成本
                                val[i] = abs(a[i] - b[i]),   // 单个箱子移动的初始成本
                                         now += val[i],               // 累加到总成本
                                                d[i] = {t[i], i};            // 配对(截止时间, 箱子编号)

        sort(d + 1, d + n + 1), s[0] = -2e9, s[n + 1] = 2e9;  // 按截止时间t_i从小到大排序

        for (LL i = 1; i <= 2 * n + 1; i++)
            fa[i] = i;        // 初始化并查集

        for (LL i = n; i; i--) { // 按截止时间从大到小处理
            LL x = d[i].second, y = 0, z = n + 1; // x是当前处理的箱子编号

            if (t[x] < now) { // 贪心检查：如果当前箱子的截止时间小于当前所需总步数
                flag = 1; // 标记为不可能
                break;
            }

            // 查找x左右相邻的、已处理过的箱子块的代表元
            y = find(x - 1), fa[x] = y,                      // 将x合并到左边的块
                                     z = find(x + n + 1), fa[x + n] = z, z -= n,  // 将x合并到右边的块
                                             now -= val[x];                               // 从总成本中移除x的独立成本

            if (b[y] >= a[y] and 1 <= y and y <= n)
                cal(y, z - 1, 0);  // 如果左边的块需要向右移动，重新计算合并后块的成本

            if (b[z] < a[z] and 1 <= z and z <= n)
                cal(z, y + 1, 1);  // 如果右边的块需要向左移动，重新计算合并后块的成本
        }

        puts(flag ? "No" : "Yes");
    }

    return 0;
}

总结

本题通过贪心策略和并查集高效地解决了箱子移动的可行性问题，结合排序和前缀和优化了成本计算。算法在时间和空间复杂度上均满足题目约束，适用于大规模数据。