-3

郵便配達停止の問題を解決しようとしていますが、それを解決するためのアルゴリズムが見つかりません。問題はこれです：

1からnまでの番号が付けられたnの家と、nの郵便配達員があり、それぞれにnの文字が各家に掲示されます。郵便局長は、各郵便局長が異なる時間に1回だけ各家を訪問するように計画を決定しました。つまり、どの家にもいつでも最大1人の郵便局長がいます。他の郵便局長のような郵便局長はいないので、郵便局長は、n軒の家に郵便局長が配達するときに他の郵便局長と会わないことを望んでいます。そこで彼は、郵便配達員が特定の家の後に投稿するのをやめたいと思っています。つまり、Postmasterは、 i番目の郵便局長がstop [i]番目の家を訪問すると、その家の後に投稿を停止するようなシーケンス停止を見つけたいと考えています。彼は各家に最大1つのポストがあることを確認したいので、シーケンスストップを選択する必要があります郵便配達員Aが時間Tに家Hを訪問し、彼が家の後に投稿を停止した場合、他の郵便配達員は時間Tの後に家Hを訪問しません。郵便局長がそのようなシーケンス停止を見つけるのを手伝ってください。

入力は次のように与えられます：

まず、 n（1≤n≤100 ）で、郵便配達員と家の数を示します。次に、n行が続き、各行にはn個の正の整数が含まれます。i行目のj番目の整数は、i番目の郵便配達員がj番目の家を訪問する時刻を示します。

例：n = 3

シーケンスは次のとおりです。

1 2 3

4 5 6

7 8 9

出力されるストップ配列は次のようになります。

3 2 1つまり、1番目の郵便配達員は3番目の家、2番目の家、3番目の家に投稿を停止します。

この問題を解決するには、どのアルゴリズムを使用する必要がありますか？

4

2 に答える 2

0

@Herokillerアルゴリズムが正しくありません。例：

1 4 2

8 6 9

5 7 3

出力は次のようになります。

ステップ1：タプル（8,7,3）の最小値を7にしてから、（8,9）を取得して最小値を8にし、最後に（2）出力を3,1,2にします。

しかし、答えは1 2 3 ie（1,6,3）になります

この質問に対する答えはわかりませんが、矛盾したテストケースがあり、正解としてマークされていたため、メッセージにコメントできませんでした。

于 2012-08-10T21:26:10.490 に答える
0

更新、私の最後の答えは間違っていました。

新しい解決策：各ステップで、各行の最小数を見つけてから、それらの最大値を取得します。これが、i番目の郵便配達員の停車地になります。次の各ステップで、その郵便配達員はもう考慮しないでください

提供したサンプルの場合：

1 2 3 
4 5 6 
7 8 9

1番目のステップは147で、最大数は7なので、3番目の郵便配達員の停車地は1番目の家（stop [3] = 1）です。その後、1列目と3行目を考慮しません。2番目のステップでは2と5が見つかります。 、最大は5なので、-stop [2] = 2; 3番目のステップの停止[1]=3;

それで、なぜそれが本当なのか、あるステップで正しい数を選択した場合、同じ列の任意の数について、それは私たちの数よりも小さい（つまり、後で問題を引き起こさない）か、私たちの数よりも大きいことがわかります、ただし、その行の番号は後で選択されるよりも少ないため、列の大きい番号は使用されません。

そして、例として@WayneRooneyが提供しました

1 4 2
8 6 9
5 7 3

1番目のステップで1、6、3を選択6を選択2番目のステップで1、3を選択3 3番目のステップ1の回答：1、2、3

于 2012-08-09T09:58:08.157 に答える