白駿2437、秤-Greedy、積算

8823 ワード
グリディ greedy 累加 アルゴリズム#アルゴリズム# てんびんで量る コーディングテスト テキストリンク

https://www.acmicpc.net/problem/2437

1.アイデア


  • n個の組み合わせられない最小重量を求めます
    ①n個の枢椎を組み合わせた「最大重量」=全枢椎の重量の和
    ②n複数の枢椎に組合わない「最大重量」=全枢椎の重量の和+1
    ③小重量~大重量の並べ替えの場合、
    隣接するピボット間の重量差が小さいほど密(?)ピボット重量と

  • 重量の小さい順にn個のピボットを並べます
    • 類推規則
  • 最軽量[0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量
    =[0]2番目のピボット[i]2番目のピボットを組み合わせた最大重量
    • ②、③の類推規則
  • ([0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量+1)<次[i+1]第1ダイヤルまでの重量
    =>([0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量+1)再構成不可

    • 2.資料構造

  • int[]:枢椎当たりの重量

    • 3.時間複雑度


  • 配列順:O(n log 2 n)
    =>n最大値代入:10^3 log 210^3=3 x 10^3 log 2~=9 x 10^3

  • 積算と重量構成:O(n)
    =>n置換最大値:10^3
    • =>総時間複雑度:O(n+n log 2 n)
    =>n導入最大値:(9 x 10^3)+10^3=10^4<1億

    コード#コード#

    import java.io.*;
import java.util.*;

public class Main {
	static int n;				// 추 개수
	static int[] weights;		// 각 추의 무게
	static int minSum;			// 출력, 입력 추 조합으로 만들 수 없는 최소 무게 합

	static void solution() {
		int sum = 0;			// 추 무게 누적합

		for (int i = 0; i < n; i++) {
			// ([0]번째 추 ~ [i]번째 추 까지의 무게 누적합 + 1) < 다음 [i+1]번째 추의 무게인 경우
			// ※ 최초 누적합(sum = 0) + 1 = 1 < weights[0] 비교하여, 무게 1 만들 수 있는지 확인
			if (sum + 1 < weights[i]) {
				// ([0]번째 추 ~ [i]번째 추 까지의 무게 누적합 + 1) 무게 구성 불가능
				minSum = sum + 1;
				return;
			}

			sum += weights[i];
		}

		// [0]번째 추 ~ [n-2]번째 추 까지의 무게 누적합을 구성 가능한 경우
		// => (모든 추의 무게 누적합 + 1) 무게 구성 불가능
		minSum = sum + 1;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		weights = new int[n];
		for (int i = 0; i < n; i++)
			weights[i] = Integer.parseInt(st.nextToken());

		Arrays.sort(weights);

		solution();
		System.out.println(minSum);
	}
}
    複素の加減乗除及び開方乗方演算
    🛒[プログラマー]多段歯ブラシ販売