Codeforces问题Binary tree and Processors的C++实现报错求助

问题重述 #

我们有一棵高度为h的满二叉树任务结构，初始只有根节点就绪。每个时间单位，p个处理器最多处理p个就绪任务；处理完成后，已执行父任务的子任务会在下一个时间单位变为就绪状态（就绪任务会保持状态直到被执行）。需要计算执行完所有任务的最少时间。

你的代码存在的问题 #

你的思路是按层依次计算时间，但这不符合任务就绪的动态规则——实际上，上层任务处理后，下层任务会陆续就绪，可与上层剩余任务同时处理，无需等整层处理完。此外还有两个技术问题：

1. 数据类型与精度问题：pow(2, q)返回double类型，当q较大时（如h=50），double无法精确表示大整数，转换为int会出错；且int无法容纳2^50这样的大数，会溢出。
2. 忽略叶子节点特性：叶子节点处理后不会产生新的就绪任务，你的代码没有区分这一点。

正确解法思路 #

我们需要模拟任务处理的动态过程，分两个阶段：

1. 处理非叶子节点：非叶子节点处理后会产生两个子节点，需跟踪当前就绪的非叶子节点数量，每次处理最多p个，更新就绪数和已完成数。
2. 处理叶子节点：所有非叶子节点处理完后，所有叶子节点都已就绪，此时只需计算处理完所有叶子节点所需的时间（向上取整）。

关键细节 #

• 用位运算计算满二叉树的节点数：1LL << h表示2^h，避免浮点精度问题和溢出。
• 非叶子节点总数：(1LL << (h-1)) - 1，叶子节点总数：1LL << (h-1)。
• 处理非叶子节点时，若当前就绪数≤处理器数，一次性处理所有就绪节点；否则每次处理p个，每次处理后就绪数增加p（因为处理p个节点会产生2p个新节点，减去已处理的p个，净增p个）。
• 处理叶子节点时，用公式(leaf_count + p - 1) / p计算向上取整的时间。

正确代码实现 #

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入，适配大量测试用例

    int t;
    cin >> t;
    while (t--) {
        int h, p;
        cin >> h >> p;
        
        if (h == 1) {
            cout << 1 << '\n';
            continue;
        }

        long long non_leaf = (1LL << (h-1)) - 1;
        long long leaf = 1LL << (h-1);
        long long ready = 1;
        long long done_non_leaf = 0;
        long long time = 0;

        // 处理所有非叶子节点
        while (done_non_leaf < non_leaf) {
            long long k = min(ready, (long long)p);
            k = min(k, non_leaf - done_non_leaf); // 不超过剩余非叶子节点数
            done_non_leaf += k;
            time++;

            if (done_non_leaf == non_leaf) {
                ready = leaf; // 所有叶子节点就绪
                break;
            }
            ready += k; // 处理k个非叶子节点，新增2k个，净增k个
        }

        // 处理叶子节点，向上取整计算时间
        long long leaf_time = (ready + p - 1) / p;
        time += leaf_time;

        cout << time << '\n';
    }
    return 0;
}

测试验证 #

• 测试用例3 1：输出7，正确。
• 测试用例3 2：输出4，正确。
• 测试用例10 6：输出173，正确。

内容的提问来源于stack exchange，提问作者Ethan Brown