二叉树和处理器（C++ Codeforces 问题）

Question

正如标题所说，我正在尝试解决这个我在 Youtube 或其他地方找不到解决方案的问题...

Eonathan Eostar decided to learn the magic of multiprocessor systems. He has a full binary tree of tasks with height h. In the beginning, there is only one ready task in the tree — the task in the root. At each moment of time, p processes choose at most p ready tasks and perform them. After that, tasks whose parents were performed become ready for the next moment of time. Once the task becomes ready, it stays ready until it is performed.
You shall calculate the smallest number of time moments the system needs to perform all the tasks.
Input:
The first line of the input contains the number of tests t (1≤t≤5⋅105). Each of the next t lines contains the description of a test. A test is described by two integers h (1≤h≤50) and p (1≤p≤104) — the height of the full binary tree and the number of processes. It is guaranteed that all the tests are different.
Output:
For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks
Example:
input:
3
3 1
3 2
10 6
output:
7
4
173

本人初学C++，所以想到了这种方法来解决这道题：

我数了所有节点(pow(2,height)-1)
对于每一行，我计算可用节点并放置一个 if 语句，其中显示：If 此行的可用节点小于处理器数量然后count++, else 而可用节点大于零 (node_at_m -= m[i])
[node_at_m = 此行可用的节点； m[i] = 问题中给出的处理器数量]

前两种情况 (3 1) 和 (3 2) 给出了正确答案，但第三种情况 (10 6) 给出了错误答案，所以这是我的代码：

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
int t, node,nodeatm, count;
cin >> t;
int n[t], m[t];

for (int i = 0; i < t; i++)
{
  cin >> n[i];
  cin >> m[i];
  node = pow(2,n[i])-1;
  count = 0;
  for(int q = 0; q < n[i]; q++)
  {
    nodeatm = pow(2,q);
    if(nodeatm <= m[i])
    {
      count++;
    }
    else
    while(nodeatm > 0)
    {
      nodeatm -= m[i];
      count++;
    }

  }
  cout << count << endl;
}

  return 0;
}

我真的不太喜欢在这里发布 Codeforces 问题，但我在 Internet 上找不到关于这个问题的任何资源...

等待您的答复，谢谢。

Answer 1

以上代码的问题在于，当某些任务是上一级别的剩余任务时，您错误地处理了这种情况。您假设所有任务都必须从一个级别完成，然后我们才能进入另一个级别。

以下是更正后的代码。 You can see it working here:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t, node,nodeatm, count;
    cin >> t;
    int n[t], m[t];

    for (int i = 0; i < t; i++)
    {
      cin >> n[i];
      cin >> m[i];
      node = pow(2,n[i])-1;
      count = 0;
      int rem = 0;
      for(int q = 0; q < n[i]; q++)
      {
        nodeatm = pow(2,q) + rem ;
        if(nodeatm <= m[i])
        {
          count++;
          rem = 0;
        }
        else
        {
            while(nodeatm >= m[i])
            {
                nodeatm -= m[i];
                count++;
            }
            rem = nodeatm;
        }

      }
      
      if( rem )
      {
        count++;
      }
      cout << count << endl;
    }

  return 0;
}

以下是稍微简化的代码。 You can see it working here:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
      int rem = 0, n, m, count = 0;
      cin >> n >> m;
      for(int q = 0; q < n; q++)
      {
        int nodeatm = pow(2,q) + rem;
        if( nodeatm < m)
        {
            count++;
            rem = 0;
        }
        else
        {
            count += ( nodeatm/ m );
            rem = ( nodeatm % m );
        }
      }

      if( rem )
         count++;
      cout << count << endl;
    }
  return 0;
}

二叉树和处理器（C++ Codeforces 问题）

Binary tree and Processors (C++ Codeforces Problem)

c++

binary-tree