「Candy Machine」题解

题目核心分析

问题本质

需要为所有糖果分配最少的收集车，使得每辆收集车能在糖果输出的时间到达对应输出槽。收集车的约束是：每秒可移动1个相邻槽位，初始位置可自由选择（无时间成本）。本质是区间图着色问题的变种，最少收集车数量等于最大重叠区间数（根据贪心算法最优解）。

关键洞察

1. 收集车可行性条件：若收集车先接糖果A（s₁, t₁），再接糖果B（s₂, t₂），必须满足 t₂ ≥ t₁ + |s₂ - s₁|（即从A到B的移动时间不超过两糖果的时间间隔）。
2. 坐标变换：将糖果的（s, t）转换为 x = s + t、y = s - t，则可行性条件等价于 x₂ ≥ x₁ 且 y₂ ≥ y₁（推导见下文）。
3. 问题转化：转换后，问题变为「给定一组点（x, y），按x升序排序后，求最长递减子序列的长度」—— 这正是最少收集车数量（与最长递增子序列长度等价，因坐标变换后单调性反转）。

坐标变换推导

原可行性条件：t₂ ≥ t₁ + |s₂ - s₁|
展开绝对值两种情况：

• 若 s₂ ≥ s₁：t₂ - t₁ ≥ s₂ - s₁ → (s₂ - t₂) ≤ (s₁ - t₁)（即 y₂ ≤ y₁）
• 若 s₂ ≤ s₁：t₂ - t₁ ≥ s₁ - s₂ → (s₂ + t₂) ≥ (s₁ + t₁)（即 x₂ ≥ x₁）

合并后，当糖果按 x = s + t 升序排序时，可行的后续糖果必须满足 y = s - t 递减。因此，不可行的糖果对会形成递增的y序列，最少收集车数量等于最长递增y子序列的长度（根据Dilworth定理）。

算法设计

核心思路

1. 坐标变换：将每个糖果（sᵢ, tᵢ）转换为（xᵢ = sᵢ + tᵢ, yᵢ = sᵢ - tᵢ）。
2. 排序：按xᵢ升序排序，x相同时按yᵢ降序排序（避免x相同的糖果形成不必要的递增子序列）。
3. 离散化：yᵢ的取值范围可能很大（-1e9~1e9），需离散化压缩到1~n的区间，便于后续树状数组操作。
4. 树状数组求最长递增子序列（LIS）：遍历排序后的糖果，用树状数组查询当前yᵢ之前的最大LIS长度，更新当前糖果的LIS长度，最终最大LIS长度即为最少收集车数量。

时间复杂度

• 坐标变换：O(n)
• 排序：O(n log n)
• 离散化：O(n log n)
• 树状数组操作：每个糖果对应1次查询和1次更新，每次操作O(log n)，总O(n log n)
• 整体复杂度：O(n log n)，可高效处理n=1e5的数据规模。

代码实现（可直接复制）

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 5e5 + 5;

// 树状数组（BIT），用于维护区间最大值，加速LIS查询
struct BIT {
    int n;
    int max_val[N];  // 存储对应位置的最大LIS长度
    void init(int _n) {
        n = _n;
        memset(max_val, 0, sizeof(max_val));
    }
    // 更新：在pos位置插入值val，维护区间最大值
    void modify(int pos, int val) {
        for (int i = pos; i <= n; i += (i & -i))
            max_val[i] = std::max(max_val[i], val);
    }
    // 查询：[1, pos]区间内的最大值
    int query(int pos) {
        int ret = 0;
        for (int i = pos; i >= 1; i -= (i & -i))
            ret = std::max(ret, max_val[i]);
        return ret;
    }
} bit;

int n;
int t[N], b[N], ans[N];  // t:时间，b:槽位，ans:每个糖果的收集车编号
struct Node {
    int x, y, id;  // x = s + t，y = s - t，id:原始糖果索引
} P[N];

int main() {
    // 加速输入输出
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    std::vector<int> disc;  // 用于y坐标离散化

    // 读取输入
    for (int i = 1; i <= n; i++)
        std::cin >> b[i] >> t[i];

    // 坐标变换 + 收集y坐标用于离散化
    for (int i = 1; i <= n; i++) {
        P[i].x = b[i] + t[i];
        P[i].y = b[i] - t[i];
        P[i].id = i;
        disc.push_back(P[i].y);
    }

    // 排序：按x升序，x相同按y降序（避免x相同的糖果形成递增子序列）
    std::sort(P + 1, P + 1 + n, [&](Node &lhs, Node &rhs) {
        return lhs.x == rhs.x ? lhs.y > rhs.y : lhs.x < rhs.x;
    });

    // y坐标离散化（压缩到1~m的区间）
    std::sort(disc.begin(), disc.end());
    disc.resize(std::unique(disc.begin(), disc.end()) - disc.begin());
    int m = disc.size();
    bit.init(m + 2);  // 树状数组大小预留冗余

    // 遍历糖果，用树状数组求LIS长度（即收集车编号）
    for (int i = 1; i <= n; i++) {
        // 找到当前y对应的离散化位置
        int p = std::lower_bound(disc.begin(), disc.end(), P[i].y) - disc.begin() + 1;
        // 查询[1, p]的最大LIS长度，当前糖果的LIS长度为该值+1（新增一辆车或接续之前的车）
        ans[i] = bit.query(p) + 1;
        // 更新树状数组：在p+1位置插入当前LIS长度（避免同y的糖果重复计数）
        bit.modify(p + 1, ans[i]);
    }

    // 输出最少收集车数量（即最大LIS长度）
    std::cout << *std::max_element(ans + 1, ans + 1 + n) << "\n";

    // 输出每颗糖果的信息（s, t, 收集车编号）
    for (int i = 1; i <= n; i++)
        std::cout << b[P[i].id] << " " << t[P[i].id] << " " << ans[i] << "\n";

    return 0;
}

代码关键模块解释

1. 树状数组（BIT）

• 功能：维护区间最大值，用于快速查询「当前y坐标之前的最长递增子序列长度」。
• init：初始化树状数组大小和存储数组。
• modify：在指定位置更新最大值，确保后续查询能获取最新结果。
• query：查询1到指定位置的最大值，即当前糖果可接续的最长子序列长度。

2. 坐标变换与排序

• 坐标变换：x = s + t、y = s - t，将收集车可行性条件转化为单调序列问题。
• 排序规则：按x升序（保证时间顺序），x相同时按y降序（x相同的糖果y递减，不会形成递增子序列，避免多分配收集车）。

3. 离散化

• 原因：y的取值范围为-1e9~1e9，无法直接作为树状数组的索引。
• 过程：将所有y值排序去重，映射到1~m的连续区间，减少空间占用并加速查询。

4. 收集车编号分配

• 遍历排序后的糖果，对每个糖果查询其y离散化位置之前的最大LIS长度，当前糖果的编号为该长度+1（表示要么接续之前的收集车，要么新增一辆）。
• 用树状数组更新当前LIS长度，供后续糖果查询。

测试样例验证

样例输入

5
1 1
2 3
1 5
3 4
2 6

步骤1：坐标变换

步骤2：排序

按x升序、x相同y降序排序后： | 排序后索引 | x | y | 原始编号 | |------------|----|----|----------| | 1 | 2 | 0 | 1 | | 2 | 5 | -1 | 2 | | 3 | 6 | -4 | 3 | | 4 | 7 | -1 | 4 | | 5 | 8 | -4 | 5 |

步骤3：离散化y值

y值集合：{0, -1, -4} → 排序去重后 { -4, -1, 0 } → 离散化映射：

• -4 → 1，-1 → 2，0 → 3

步骤4：树状数组计算LIS

步骤5：结果

• 最大LIS长度为2（最少收集车数量）。
• 每个糖果的收集车编号与ans一致，输出结果与样例完全匹配。