スタンダードカラーボール(10800)

カラーボール

1.ヒント

1)小さい球から計算を開始すると、ある球を計算する際に、以前に入れた球が自分の球よりも小さいか等しいので、容易に実施することができる。

2)(これまでに算出された球の大きさである現在算出された球と色が同じ球の大きさの和を算出する)は、iii番目の球を持つプレイヤーが捉えることができる全ての球の大きさの和を算出することができる。

3)しかし問題は同じ大きさの球が存在することである。幸いなことに、サイズの範囲は1≦Si≦20001les ile 20001≦Si≦2000であるため、サイズ別に分類して格納することができる。これにより、実施がより容易になる。

2.近接

順序を強制できますか?

順序の影響を受けない演算がある場合、任意にソートできます.これにより、実装が簡略化されます.
この問題では,最小の球から順に計算し,これまで計算した球の大きさの和pppを保つことで,現在計算する球よりも小さい球の大きさの和が分かる.もちろん、同じ大きさのボールもあるので、処分すべきです.同じサイズを除外する場合は、色ごとにサイズの和を格納する配列CCCを維持します.これにより、読み込みのたびにO(N)O(N)O(N)O(N)O(N)の検索を実行する必要がなくなります.
問題はSiS iSiの範囲が小さいことである.サイズ別に格納された2 Dアレイを使用すると、より容易に実装できます.

3.実施

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		// S[x] = x크기인 컬러볼들 (번호, 색)
		ArrayList<ArrayList<Pair>> S = new ArrayList<>(2001);
		for (int i = 0; i <= 2000; i++) S.add(new ArrayList<>());
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			S.get(s).add(new Pair(i, c));
		}
		int p = 0; // 지금까지 계산한 공들의 크기의 합
		int[] C = new int[N + 1]; // 색깔별 크기들의 합 저장
		int[] ret = new int[N + 1]; // i번째 공이 집을수 있는 공의 크기 합 저장
		for (int i = 1; i <= 2000; i++) {
			for (Pair x : S.get(i)) ret[x.num] = p - C[x.color];
			p += S.get(i).size() * i;
			for (Pair x : S.get(i)) C[x.color] += i;
		}
		for (int i = 1; i <= N; i++) bw.append(ret[i]).append("\n");
		System.out.print(bw);
	}

}
class Pair {
	int num, color;
	
	Pair (int n, int c) { num = n; color = c; }
}

1）時間複雑度

O(N)O(N)O(N)中間には2つのfor文が表示されますが、同じ要素を複数回計算しないため、合計時間の複雑さは球の個数に等しくなります.