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

「b」のボスは「e」なので、正解は「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

階層用のツリーのセットを構築してから、深さ最後のトラバーサルを実行したいようです。

トップボスの候補はボスのいない者だけ。したがって、データ構造はこれを簡単に記録する必要があります。(階層に常に 1 人のトップ ボスがいる場合は、ボスのいない固有の個人を返すだけで問題を解決できます。)

std::multimapということで、上司から部下への提案です。null/空の名前をマップに入れると、上位のボスが返されます。

スタックを保持するか、関数再帰を使用して組織図の上から下に移動し、下から上に戻るトリップで階層のサイズを合計します。

于 2012-12-19T04:23:06.667 に答える
0

コードを可能な限り同じに保ちたい場合は、これを変更できます。

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

これに

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

しかし、名前が上司の上司に属する階層を考慮していないため、これでも問題は解決していません。

于 2012-12-19T04:49:04.877 に答える
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 に答える