程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 558C Amr and Chemistry 規律

Codeforces 558C Amr and Chemistry 規律

編輯：關於C++

題目鏈接

題意：

給定n長的序列

每次可以選一個數讓其 *=2 或者 /=2

問至少操作多少次使得所有數相等。

思路：

對於每個數，計算出這個數可以變成哪些數，以及變成那個數的最小步數。

cnt[i] 表示序列中有cnt個數可以變成i

step[i] 表示能變成i的那些數變成i的花費和是多少。

notice: if a[i] == 7, a[i] also can reach 6. by /=2 then *=2

7->3->1..

3->6->12

1->2->4

只要是奇數（不包括1）就能花費2步到達 a[i]-1的位置

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair pii;
const int N = 200005;
const int inf = 1e9 + 10;
int n;
int a[N];
int cnt[N], step[N];
void up(int y, int s) {	//向上枚舉
	while (y < N) {
		cnt[y]++;
		step[y] += s;
		y <<= 1;
		s++;
	}
}
void go(int y) {
	up(y, 0);
	int now = 1;
	while (y) { //使y一直向下減小
		if ((y > 1) && (y & 1)) {
			y >>= 1;
			up(y, now);
		}
		else {
			y >>= 1;
			cnt[y]++; step[y] += now;
		}
		now++;
	}
}
int main() {
	while (cin >> n) {
		memset(cnt, 0, sizeof cnt); memset(step, 0, sizeof step);
		for (int i = 1; i <= n; i++) {
			rd(a[i]);
			go(a[i]);
		}
		int ans = step[1];
		for (int i = 2; i < N; i++) {
			if (cnt[i] == n)
				ans = min(ans, step[i]);
		}
		pt(ans);
	}
	return 0;
}