有一个长为 \(n\) 的数组，可以执行以下整份操作任意次：
- 选择任意两个数 \(a_i, a_j\) ，满足 \(2 \mid a_i\)
- \(a_i = \frac{a_i}{2}\)
- \(a_j = 2 \cdot a_j\)
请找到经过任意此操作后的最大 \(\sum_{i=1}^{n} a_i\) 。
在唯一分解定理下讨论两个数 \(a_i = 2^{\alpha_i} \cdot x, a_j = 2^{\alpha_j} \cdot y\) 。显然有
\[2^{\alpha_i} \cdot x + 2^{\alpha_j} \cdot y \leq
x + 2^{\alpha_j + \alpha_i} \cdot y
\]
加号变乘号更优。
于是提取出所有 \(a_i\) 的 \(2\) 的幂次 \(tot\) 。此时将 \(2^{tot}\) 统一贡献到 \(max(a_i)\) 的位置最优。
时间复杂度 \(O(w n)\) ，但是数据范围可能会很大。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::vector<long long> a(n+1);
int cnt = 0; for (int i = 1; i <= n; i++) {
std::cin >> a[i];
int t = __builtin_ctzll(a[i]);
a[i] >>= t; cnt += t;
}
int l = std::max_element(a.begin()+1, a.end()) - a.begin(); a[l] <<= cnt;
long long sum = 0; for (int i = 1; i <= n; i++) sum += a[i];
std::cout << sum << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}