Codeforces Round #312 Div2 C: Amr and Chemistry

問題

codeforces.com

解法

  • 最終的な値が入力の最大値を超えることはない。
  • aとbが一致するまで大きい方を1/2ずつしていった時の最終的な値をM(a,b)とすると、最終的な値はM(a0,a1,a2,...)を2の累乗倍したものである。

コード

import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] a = new int[N];

		int minMatch = 1;
		int max = 0;
		for (int i = 0; i < N; i++) {
			a[i] = scanner.nextInt();
			if (i == 0) {
				minMatch = a[0];
			} else {
				minMatch = getmatch(minMatch, a[i]);
			}

			max = Math.max(max, a[i]);
		}
		scanner.close();

		int minSteps = Integer.MAX_VALUE;
		for (int finalValue = minMatch; finalValue <= max; finalValue <<= 1) {
			int steps = 0;
			for (int i = 0; i < N; i++) {
				steps += steps(a[i], finalValue);
			}

			minSteps = Math.min(minSteps, steps);
		}
		System.out.println(minSteps);
	}

	// xとyを1/2ずつしていって一致するまでの操作数を返す
	private int steps(int x, int y) {
		int ret = 0;
		int prematch = getmatch(x, y);

		while (x > prematch) {
			ret++;
			x >>= 1;
		}
		while (y > prematch) {
			ret++;
			y >>= 1;
		}

		return ret;
	}

	// aとbを1/2ずつしていった時の一致した数を返す
	private int getmatch(int a, int b) {
		while (a != b) {
			if (a > b)
				a >>= 1;
			else
				b >>= 1;
		}

		return a;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}