二叉树和处理器(c++ Codeforces问题)

Question

正如标题所说，我正在努力解决这个问题，我在Youtube或其他地方找不到解决方案…

问题说明如下:

Eonathan Eostar决定学习多处理器系统的魔力。他有一个高度为h的任务的完整二叉树。一开始，树中只有一个准备好的任务——根节点上的任务。在每个时刻，p个进程最多选择p个就绪任务并执行它们。在那之后，父母完成的任务为下一个时刻做好了准备。一旦任务准备好了，它就会一直保持准备状态，直到它被执行。
您应该计算系统执行所有任务所需的最小时间矩。输入:

输入的第一行包含测试次数t(1≤t≤5⋅105)。接下来的每一行都包含一个测试的描述。一个检验用两个整数h(1≤h≤50)和p(1≤p≤104)来描述，这两个整数分别是全二叉树的高度和进程数。可以保证所有的测试都是不同的。输出:

对于每个测试输出，在单独的行上有一个整数—系统执行所有任务所需的最小时间瞬间数
示例:输入:

3
3 2 1
3
10 6
输出:
7
4
173

我是一名新的c++初学者,所以我认为这种方式来解决这个问题:

1. I count all nodes(pow(2,height)-1)
2. 对于每一行，我计算可用节点并放入if语句，该语句表示:if这一行的可用节点小于处理器数，然后count++，else而可用节点大于0(node_at_m -= m[i])
   [node_at_m=本行可用的节点;m[我]=问题中给出的处理器数量]

对于前两种情况，即(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问题，但是我在互联网上找不到任何关于这个问题的资源…

等待您的回答，谢谢。

Answer 1

上面代码的问题是，当一些任务从上一级保留时，您正在错误地处理这种情况。你是假设所有任务之前必须完成从一个水平到另一个水平。

以下是更正后的代码。你可以看到它在这里工作:

#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;
}

下面是稍微简化的代码。你可以看到它在这里工作:

#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;
}