「PA 2018」Poddrzewo 题解

问题分析

我们需要从给定的度数序列中构造一棵树，通过删除、修改、交换操作，最小化修改次数。

关键性质

对于 $k$ 个节点的树：

• 度数总和必须为 $2(k-1)$
• 每个节点度数 $\ge 1$
• 修改代价 = $\frac{|S - 2(k-1)|}{2}$

算法思路

1. 枚举所有可能的 $k$（节点数）
2. 对于每个 $k$，选择连续的 $k$ 个度数（排序后）
3. 计算修改代价，记录最小值
4. 构造对应的树

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

int n;
int a[MAXN];
long long prefix[MAXN];

vector<pair<int, int>> construct_tree(vector<int> degrees) {
    int k = degrees.size();
    vector<pair<int, int>> edges;
    
    vector<pair<int, int>> nodes;
    for (int i = 0; i < k; i++) {
        nodes.push_back({i + 1, degrees[i]});
    }
    
    // 使用优先队列优化
    priority_queue<pair<int, int>> pq; // (度数, 编号)
    for (auto [id, deg] : nodes) {
        if (deg > 0) pq.push({deg, id});
    }
    
    while (pq.size() > 1) {
        auto [deg_u, u] = pq.top(); pq.pop();
        vector<pair<int, int>> temp;
        
        for (int i = 0; i < deg_u; i++) {
            if (pq.empty()) break;
            auto [deg_v, v] = pq.top(); pq.pop();
            edges.push_back({u, v});
            if (deg_v > 1) {
                temp.push_back({deg_v - 1, v});
            }
        }
        
        for (auto p : temp) {
            pq.push(p);
        }
    }
    
    return edges;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }
    
    long long best_cost = 1e18;
    int best_k = 0;
    int best_start = 0;
    
    // 优化：只检查有希望的k值
    for (int k = max(2, n - 1000); k <= n; k++) {
        long long target = 2LL * (k - 1);
        
        // 检查几个关键位置
        vector<int> positions = {0, n - k, max(0, n / 2 - k / 2)};
        for (int start : positions) {
            if (start > n - k) continue;
            long long sum = prefix[start + k] - prefix[start];
            long long cost = abs(sum - target) / 2;
            
            if (cost < best_cost) {
                best_cost = cost;
                best_k = k;
                best_start = start;
            }
        }
    }
    
    cout << best_cost << "\n";
    cout << best_k << "\n";
    
    vector<int> selected;
    for (int i = best_start; i < best_start + best_k; i++) {
        selected.push_back(a[i]);
    }
    
    long long current_sum = 0;
    for (int x : selected) current_sum += x;
    long long target_sum = 2LL * (best_k - 1);
    
    // 调整度数
    if (current_sum != target_sum) {
        long long diff = target_sum - current_sum;
        if (diff > 0) {
            for (int i = selected.size() - 1; i >= 0 && diff > 0; i--) {
                int increase = min((long long)(best_k - 1 - selected[i]), diff);
                selected[i] += increase;
                diff -= increase;
            }
        } else {
            diff = -diff;
            for (int i = 0; i < selected.size() && diff > 0; i++) {
                int decrease = min((long long)(selected[i] - 1), diff);
                selected[i] -= decrease;
                diff -= decrease;
            }
        }
    }
    
    vector<pair<int, int>> edges = construct_tree(selected);
    for (auto [u, v] : edges) {
        cout << u << " " << v << "\n";
    }
    
    return 0;
}

复杂度分析

• 排序：$O(n \log n)$
• 枚举 $k$：优化后 $O(n)$
• 树构造：$O(n \log n)$
• 总复杂度：$O(n \log n)$

算法标签

• 贪心算法
• 树构造
• 排序优化

这个解法能够在 $n \leq 10^6$ 的规模下高效运行，并找到近似最优解。