「CCO 2024」Pizza Party 题解

算法思路

问题转化

本题的核心是将披萨分配问题转化为**最长递增子序列（LIS）**问题。

设推车上的披萨序列为 $a_1, a_2, \ldots, a_N$，参与者需求序列为 $b_1, b_2, \ldots, b_N$。

关键观察：

1. 可行性条件：对于每种口味 $i$，推车中该口味的披萨数量必须等于需求该口味的参与者数量。
2. 顺序匹配：第 $j$ 个需求口味 $b_j$ 的参与者，必须匹配推车中最后一个可用的该口味披萨（因为披萨是从顶部开始取的）。

算法步骤

步骤1：建立位置映射

对于每种口味 $i$：

• 记录推车中该口味披萨的位置：$pa[i] = \text{位置列表}$
• 记录需求该口味的参与者位置：$pb[i] = \text{位置列表}$

建立映射 $p$：$p[pb[i][j]] = pa[i][\text{len}(pa[i]) - j - 1]$

• 这表示第 $j$ 个需求口味 $i$ 的参与者对应推车中倒数第 $j$ 个该口味的披萨

步骤2：计算最小摞数

最小摞数 $K$ 等于序列 $p$ 的最长递增子序列长度。

证明思路：

• 每个摞对应一个递增子序列
• 序列 $p$ 的 LIS 长度即为所需的最小摞数

步骤3：构造方案

• $f[i]$：以位置 $i$ 结尾的 LIS 长度（即参与者 $i$ 所在的摞编号）
• $g[i]$：披萨 $i$ 所在的摞编号

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自线段树的区间查询和更新
• 空间复杂度：$O(N)$，用于存储各种数组和线段树

代码实现详解

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

// 线段树用于高效计算LIS
class segtree {
private:
    vector<pii> B;  // 节点区间
    vector<int> S;  // 区间最大值
    
    inline void pushup(int u) {
        S[u] = max(S[u << 1], S[u << 1 | 1]);
    }
    
public:
    segtree(int n) {
        B.resize(n << 2), S.resize(n << 2);
        // 建树
        function<void(int, int, int)> build = [&](int u, int l, int r) {
            if (B[u] = make_pair(l, r); l == r) return;
            int m = l + r >> 1;
            build(u << 1, l, m), build(u << 1 | 1, m + 1, r);
        };
        build(1, 0, n - 1);
    }
    
    void update(int u, int p, int x) {
        if (B[u].first == B[u].second) {
            S[u] = x;
            return;
        }
        int m = B[u].first + B[u].second >> 1;
        update(u << 1 | (p > m), p, x);
        pushup(u);
    }
    
    int query(int u, int l, int r) {
        if (l > r || B[u].first > r || B[u].second < l) return 0;
        if (l <= B[u].first && B[u].second <= r) return S[u];
        return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n), b(n), p(n);
    vector<vector<int>> pa(n), pb(n);
    
    // 读入并记录披萨位置
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pa[--a[i]].emplace_back(i);
    }
    
    // 读入并记录参与者位置
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        pb[--b[i]].emplace_back(i);
    }
    
    // 检查可行性并建立映射
    for (int i = 0; i < n; i++) {
        if (pa[i].size() != pb[i].size()) {
            cout << "-1\n";
            return 0;
        }
        // 建立参与者到披萨的映射
        for (int j = 0; j < pa[i].size(); j++) {
            p[pb[i][j]] = pa[i][pa[i].size() - j - 1];
        }
    }
    
    // 计算LIS（最小摞数）
    vector<int> f(n), g(n);
    segtree t(n);
    
    for (int i = 0; i < n; i++) {
        f[i] = t.query(1, 0, p[i]) + 1;  // 查询[0, p[i]]的最大值
        g[p[i]] = f[i];                  // 记录披萨的摞编号
        t.update(1, p[i], f[i]);         // 更新线段树
    }
    
    // 输出结果
    cout << *max_element(f.begin(), f.end()) << endl;
    
    for (int i = 0; i < n; i++)
        cout << g[i] << " \n"[i + 1 == n];
    
    for (int i = 0; i < n; i++)
        cout << f[i] << " \n"[i + 1 == n];
    
    return 0;
}

示例分析

对于样例1：

输入：
7
1 2 3 2 2 1 3
2 3 1 2 3 2 1

处理过程：
1. 建立映射p: [1→6, 2→0, 3→2, 4→4, 5→1, 6→5, 7→3]
2. 计算LIS得到最小摞数K=2
3. 输出分配方案

该算法通过巧妙的转化，将复杂的披萨分配问题转化为经典的LIS问题，实现了高效求解。