の二大要素の検索(「?」、さもなければ印刷)<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);
}
}
ちょうどそれを並べ替え、2つを最後から外します。あなたの教授がそれが効率的ではないと言ったら、時期尚早の最適化はすべての悪の根源だと教えてください。 –
@EdPlunkett私は知っていますが、それはO(nlogn)であり、これはO(n)です。私たちは一回のパスで3〜5回比較します – RE60K
@EdPlunkett実際にあなたはポイントを持っています – RE60K