【题解】ICPC2022济南站 A - Tower

题目链接

https://codeforces.com/gym/104076/problem/A

题目大意

给定长度为 \(n\) 的序列 \(\{ a_n\}\) ，移去其中长度为 \(m\) 的子序列，对于剩下的元素能进行如下三种操作（无顺序和次数限制）：

• 加 \(1\)
• 减 \(1\)
• 除以 \(2\) 并向下取整

问最少进行多少次操作能把这些数变相同。

数据范围

• \(1\le n \le 500 , 0 \le m < n, 1\le a_i \le 10^{9}\)

解题思路

参考代码

const int MAXN = 5e2 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
int n, m;
int a[MAXN];
 
int fstep(int x, int cur) {
	if (x >= cur) {
		return x - cur;
	}
	int s = 0, lstc = cur;
	while (cur > x) {
		lstc = cur;
		cur >>= 1;
		s++;
	}
	assert(cur != 0);
	int res = min(s + (x - cur), (s - 1) + (lstc - x));
	return res;
}
 
ll calc(int x) {
	vector<int> vec;
	for (int i = 1; i <= n; i++) {
		int step = fstep(x, a[i]);
		vec.push_back(step);
	}
	ll res = 0;
	sort(vec.begin(), vec.end());
	for (int i = 0; i < n - m; i++) {
		res += vec[i];
	}
	return res;
}
 
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	ll ans = INF;
	for (int i = 1; i <= n; i++) {
		int x = a[i];
		while (x) {
			ans = min(ans, calc(x));
			x >>= 1; 
		}
	}
	printf("%lld\n", ans);
}
 
int main() {
	int T;
	cin >> T;
	while (T--) solve();
	return 0;	
}