2016-04-02 38 views
0

の二大要素の検索(「?」、さもなければ印刷)<a href="http://codeforces.com/contest/659/problem/B" rel="nofollow">Problem</a>の配列

検索と二人の学生のユニークなチームを印刷し、各領域からn個の領域のうち、より高いスコアに基づいて(0から800)

-1と-1のスコアで初期化された、最大の要素と2番目に大きな要素を追跡できると思っていました。スコアが最大を超えている場合には、最大で現在のことと二番目に大きいの最大をシフトしなければならない

  • が、最大で二番目に大きいと同じであれば、チームは2で形成することができる。そこだけいくつかの可能性があります方法は未定義です。
  • それ以外の場合は、スコアが2番目以上の場合は、直接彼を置き換えます。エルス
  • スコアが秒と同じであれば、その後も

を未定義しかし、それは、これは間違っているが、私はなぜ知らないようですか?

コード:重複する値一度遭遇してきたとund[r]フィールドがtrueに設定されている、2つのより高い値が検出されたとき

import java.util.Arrays; 
import java.util.Scanner; 

public class B659 { 
    private static Scanner sc = new Scanner(System.in); 

    public static void main(String[] args) { 
    int n = num(); 
    int m = num(); 
    String[] rgn1 = new String[m]; // students with highest score in their region 
    String[] rgn2 = new String[m]; // students with second-highest score in their region 
    int[] rgn1s = new int[m]; // highest score in the regions 
    int[] rgn2s = new int[m]; // second-highest score in the regions 
    Arrays.fill(rgn1s, -1); 
    Arrays.fill(rgn2s, -1); 
    boolean[] und = new boolean[m]; 
    for (int i = 0; i < n; i++) { 
     String sn = str(); 
     int r = num() - 1; 
     int sc = num(); 
     if (sc > rgn1s[r]) { 
     if (rgn2s[r] == rgn1s[r] && rgn1s[r] != -1) { 
      und[r] = true; 
      continue; 
     } else { 
      rgn2s[r] = rgn1s[r]; 
      rgn2[r] = rgn1[r]; 
     } 
     rgn1s[r] = sc; 
     rgn1[r] = sn; 
     } else if (sc > rgn2s[r]) { 
     rgn2s[r] = sc; 
     rgn2[r] = sn; 
     } else if (sc == rgn2s[r]) { 
     und[r] = true; 
     } 
    } 
    for (int i = 0; i < m; i++) { 
     print((!und[i]) ? (rgn1[i] + " " + rgn2[i]) : "?"); 
    } 
    } 

    private static int num() { 
    return sc.nextInt(); 
    } 

    private static String str() { 
    return sc.next(); 
    } 

    private static void print(Object x) { 
    System.out.println(x); 
    } 
} 
+1

ちょうどそれを並べ替え、2つを最後から外します。あなたの教授がそれが効率的ではないと言ったら、時期尚早の最適化はすべての悪の根源だと教えてください。 –

+0

@EdPlunkett私は知っていますが、それはO(nlogn)であり、これはO(n)です。私たちは一回のパスで3〜5回比較します – RE60K

+0

@EdPlunkett実際にあなたはポイントを持っています – RE60K

答えて

1

あなたのコードでは、状況を処理しません。
ラム1 200
シャム1 200
ラジュ2 200
リタ1 300
ヘラ2 500
シタ1 500

:例えばのために

重複エントリが最後のペアである場合、重複エントリの一部である場合は、ifを再定義し、別のエントリを追加する必要があります。
ラム1 200
シャム1 300
ラジュ2 200
リタ1 500
ヘラ2 500
シタ1 500

:例えばのために

else if (sc == rgn1s[r]) { 
     und[r] = true; 
     } 

関連する問題