3

オンラインの審査員ページに参​​加して問題を解決しましたが、プログラムを間に合わせることができません。コードは次のとおりです。

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Set l = new HashSet();
String line;
String[] numStr;
 while(true){
  line = in.readLine();      
  numStr = line.split("\\s");      
  int a = Integer.parseInt(numStr[0]);
  if(a == 0){
     System.exit(0);
  }
  int n = 0;
  int b = Integer.parseInt(numStr[1]);
  l.clear();
  for(int i=0;i<a;i++){
    l.add(in.readLine());
  }
  for(int i=0;i<b;i++){
    if(l.contains(in.readLine())){
      n++;
    }
  }
  System.out.println(n);

200万アイテムのテストケース（numStr = "1000000 1000000"）で、1.5秒未満で実行できるようになりましたが、テストケースには十分ではないようです（3000msと表示されています）。そして今、どうすればもっと速くできるかわかりません。どんな助けでも大歓迎です！

問題：http ：//coj.uci.cu/24h/problem.xhtml？abb = 1438

4

3 に答える 3

7

入力仕様の「昇順」の部分が重要です。両方のリストが事前に並べ替えられているため、最初のリストを配列に読み込んでから、最後の項目の場所から最後の項目までのバイナリ検索を使用できます。一致するかどうかを決定する配列。実際、最初の配列の線形検索でも、最大で1回トラバースする必要があるため、機能する可能性があります。

于 2012-05-19T01:27:28.207 に答える
1

最初の入力行が1000000 0;だったとします。プログラムは百万の値を読み取ってハッシュに入力しますが、検索する値がないため、出力は0であることが保証されます。これは明らかに必要以上に時間がかかります（読み取る必要がありますが、それらをハッシュに保存しないでください）。

また、最初の値が0であることを確認するだけで終了します。仕様により、0 10000000の出力を生成する必要がありますが、プログラムは終了します。裁判官はこれをチェックしていないかもしれませんが、そうすることは合法です。

于 2012-05-19T01:46:08.743 に答える
1

データがソートされているため、マージ処理に適しています

つまり、処理するロジックは

Read Jacks records into array

While (More of jacks record to process)
  and (More of Jills record to process)  {

      if ( jacks_Record < Jills_Record)
         Jacks_Array_Index += 1;
      else if ( jacks_Record > Jills_Record)
         Read the next Jills_Record from the file
      else
         Match processing
}

ファイルのパスは1つだけで、検索はありません。二分探索の方が速い場合があります

また、BufferedReaderで大きなバッファーを指定する価値があるかもしれません

于 2012-05-19T02:27:30.267 に答える