[NICA #2] 爱与不爱

Light_Star_RPmax_AFO · 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;
}