自动搬运

查看原文

来自洛谷，原作者为

	Light_Star_RPmax_AFO 踏破千山去，直上九重天

搬运于2025-08-24 21:15:22，当前版本为作者最后更新于2023-08-22 13:55:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[NICA #2] 爱与不爱

$\mathcal{Update\ 2024.3.13}$

简化一下思路。

前言

本题第一篇题解。

传送门

题目描述

给出一个 $n$ 和一个序列 $a$，你可以让 $a_i(i \in [1,n])$ 变成 $\lfloor \frac{a_i}{2} \rfloor (\lfloor \frac{a_i}{2} \rfloor \ne 0)$ 并且将 $a_j(j \in [1,n])$ 变成 $a_j \times 2$，求序列和的最小值。

注：$\log_2 n$ 代表 $n$。

简化思路

考虑将所有数优化到最小值：

随便选取两个数 $n, m$，则可以先将其中一个数的权值赋给另一个数，最终会得到 $1,m \times 2^{\lfloor\log_2 n\rfloor}$ 同理，我们最后可以化为 $2^{\lfloor\log_2 n\rfloor}, 2^{\lfloor\log_2 m\rfloor}$，当我们有 $2, 8$ 时，易得有贪心思路。

让他们差尽可能最小化。

抽屉原理，当数列为 $x, y, z$ 时，我们总共会有 $\lfloor\log_2 x\rfloor+\lfloor\log_2 y\rfloor + \lfloor\log_2 y\rfloor$ 个 $2$ 可以分配，差最小，合理分配即可。

思路

我们可以思考若 $a_i = 2 \times 5 \times 9$，那么 $a_i$ 变成后最小的 $a_i = 2 ^ {(\lfloor\log_2 2\rfloor + \lfloor \log_2 5\rfloor + \lfloor\log_2 9\rfloor)}$，也就是 $Min = 2^{\lfloor\log_2 a_i \rfloor}$。

那么我们就可以得到最小的 $\prod_{i = 1}^n a_i$，也就是原序列中的 $2^{\sum_{i = 1}^ n \lfloor\log_2 a_i\rfloor}$。

积不变，差小和小。

我们考虑分配这些 $2$，最后得到的就是平分后的数 $sum$ 和剩余的 $2$ 的个数 $cnt = {\lfloor\log_2 {(\prod_{i = 1}^n a_i)}\rfloor} - sum \times n$，再将 $cnt$ 个 $2$ 分到每个值中，所组成的式子 $2^{sum} \times (n - cnt) + 2^{sum + 1} \times cnt$。

警钟敲烂

不开 long long 见祖宗。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
	int x = 0,f = 1;char ch = getchar();
	while (ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

inline int _2(int x){
	int ans = 0;
	while(x != 1){
		x >>= 1;
		ans++;
	}
	return ans;
}

int n, ans, a;

signed main(){
	n = read();
	for(int i = 1;i <= n;i++)
		a = read(),ans += _2(a);
	int sum = ans / n, cnt = ans - (sum * n);
	cout << (1 << sum) * (n - cnt) + (1 << sum + 1) * cnt;
    return 0;
}