0

更新：

我已经修复了代码，以便我能想出的每个测试用例都给了我正确的结果，但我仍然缺少一些东西，因为在线法官仍然说它是错误的。我在本段之后立即包含了代码。我知道我采取的方法很丑陋而且效率不高，但我不在乎。我现在只想输出正确的答案。

#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

我已经编写了代码，它适用于问题中提供的示例测试用例（输出拿破仑）。它在我抛出的其他一些测试用例中也有效，但是当我使用这个测试用例时它不起作用，例如：

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

3 回答 3

1

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

顶级老板的唯一候选人是没有老板的人。所以数据结构应该很容易记录这一点。（如果层次结构总是有一个最高老板，那么你可以简单地通过返回没有他自己的老板的唯一个人来解决问题。）

所以我建议std::multimap从老板到下属。将空/空名称放入地图会返回顶级 Boss。

保留一个堆栈或使用函数递归从组织结构图的顶部导航到底部，然后在从底部到顶部的回程中将层次结构的大小相加。

于 2012-12-19T04:23:06.667 回答
0

老板数的计算，

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]]++;
        }
    }

对我来说似乎错了。

它看起来像“对于每个下属 U：增加所有不是 U 的老板的老板数”。

无论如何，一个简单的方法来计算老板数是使用std::multiset. 每次名称作为下属出现时，将其添加到多重集中。多重集中每个名字的最终计数就是这个人拥有的老板数，只有顶级老板有0个老板。

于 2012-12-19T04:41:24.210 回答
0

如果你真的想保持你的代码尽可能相似，你可以改变这个：

    if (bosses[i] != (*it).first)
    {
        bossCount[bosses[i]]++;
    }

对此

    if (bosses[i] == (*it).second)
    {
        bossCount[bosses[i]]++;
    }

但这仍然没有解决你的问题，因为你没有考虑名字属于他们老板的老板的层次结构。

于 2012-12-19T04:49:04.877 回答