c++ - 在老板层次结构中找到“顶级”老板仅适用于某些测试用例

更新：

我已经修复了代码，使我可以提出的每个测试用例都给了我正确的结果，但是我仍然缺少一些东西，因为在线法官仍然说错了。我已在本段之后立即添加了代码。我知道我采用的方法很丑陋，效率也不高，但是我不在乎。我只希望它现在输出正确的答案。

#include <iostream>
#include <map>
#include <string>
#include <queue>

using namespace std;

int main()
{
map<string, string> names;
map<string, int > bossCount;

vector<string> bosses;
string topBoss;
int n;
int max = 0;

cin >> n;

for (int i = 0; i < n; i++)
{
    bool add = true;
    string c1, c2;
    cin >> c1 >> c2;
    names[c1] = c2;
    for (int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == c2)
            add = false;
        //bosses.push_back(c2);
    }
    if (add == true)
        bosses.push_back(c2);
}

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for(int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == (*it).second)
        {
            bossCount[bosses[i]]++;
        }
    }

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for (int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == (*it).first)
        {
            bossCount[bosses[i]] = 0;
            bossCount[(*it).second]++;
        }
    }

for (map<string, int>::iterator it = bossCount.begin(); it != bossCount.end(); it++)
{
    if((*it).second == max)
    {
        if ((*it).first < topBoss)
            topBoss = (*it).first;
    }

    if ((*it).second > max)
    {
        max = (*it).second;
        topBoss = (*it).first;
    }
}

cout << topBoss;

return 0;
}

我得到了一个唯一的名字和他们要向其报告的老板的列表（老板不是唯一的）。然后，我必须找到哪个老板具有最高的等级。这意味着列表中的几个首个唯一名称可能具有相同的老板，但是该老板可以拥有自己的老板，这意味着首个唯一名称会响应其老板的老板，因此老板的老板会赢得等级。这是整个问题：http://i.imgur.com/nyTgW.png

我已经编写了代码，并且可以在问题中提供的示例测试用例中工作（输出Napoleon）。它在我抛出的其他一些测试用例中也起作用，但是当我使用此测试用例时，它就不起作用，例如：

4
a b
c b
d b
b e

我相信正确的答案应该是“ e”，因为“ b”的老板是“ e”。我的程序在此测试用例中输出b。有人可以在这里帮助您发现问题吗？

#include <iostream>
#include <map>
#include <string>
#include <queue>

using namespace std;

int main()
{
map<string, string> names;
map<string, int > bossCount;

queue<string> next;
vector<string> bosses;
string topBoss;
    int n;
int max = 0;

cin >> n;

for (int i = 0; i < n; i++)
{
    string c1, c2;
    cin >> c1 >> c2;
    names[c1] = c2;
    bosses.push_back(c2);
}

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for(int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] != (*it).first)
        {
            bossCount[bosses[i]]++;
        }
    }

for (map<string, int>::iterator it = bossCount.begin(); it != bossCount.end(); it++)
{
    if((*it).second == max)
    {
        if ((*it).first < topBoss)
            topBoss = (*it).first;
    }

    else if ((*it).second > max)
    {
        max = (*it).second;
        topBoss = (*it).first;
    }


}

cout << topBoss;

return 0;
}

最佳答案

听起来您想为层次结构构建一组树，然后进行深度倒数遍历。

最高老板的唯一候选人是没有老板的候选人。因此，数据结构应轻松记录下来。 （如果层次结构中始终只有一个最高老板，那么您可以简单地通过返回唯一的个人而没有自己的老板来解决问题。）

因此，我建议从老板到下属的std::multimap。在地图中放置一个空/空名称将返回最高老板。

保留堆栈或使用功能递归从组织结构图的顶部导航到底部，然后在从底部到顶部的回程中累加层次结构的大小。

关于c++ - 在老板层次结构中找到“顶级”老板仅适用于某些测试用例，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13945356/