合成游戏

https://iai.sh.cn/problem/45

题目描述

有很多合成类的游戏都有如下的玩法：玩家会得到很多数字，每个数字都是 22 的幂，玩家可以挑选两个一样大的数字，将它们合成一个新的数字，新数字为原数字的两倍大小。如果这种合成操作可以不断地进行，给定小爱在最初获得的数字集合，请帮她算一下能够获得的最大数字。

2 的幂是指只有 2作为素因子的正整数。如 4、256 等等。但 60 不是，因为它有素因子 3。

输入格式

第一行：单个正整数 nn，表示小爱一开始拥有的数字数量；
第二行：nn 个正整数 a1,a2,⋯ ,ana1​,a2​,⋯,an​，表示刚开始时获得的数字，保证每个数字都是 22 的幂。

输出格式

单个正整数：表示最后可以得到的最大数字大小。

数据范围

• 对于 30%30% 的数据，1≤n≤1001≤n≤100，1≤ai≤1281≤ai​≤128；
• 对于 60%60% 的数据，1≤n≤20001≤n≤2000，1≤ai≤2201≤ai​≤220；
• 对于 100%100% 的数据，1≤n≤1,000,0001≤n≤1,000,000，1≤ai≤2401≤ai​≤240；

换底背景知识

换底公式是一个数学公式，它可以让你把一个对数的底数换成另一个对数的底数。¹

换底公式的英文是 change of base formula。²³

换底公式的形式是 log_b(x) = log_a(x) / log_a(b)，其中 a 和 b 都是大于零而不等于一的常数，x 是一个正数。¹²

这个公式的意思是，如果你想计算以 b 为底的 x 的对数，你可以用以 a 为底的 x 的对数除以以 a 为底的 b 的对数来得到。²

例如，如果你想计算以 2 为底的 8 的对数，你可以用换底公式把它变成以 10 为底的对数：

log_2(8) = log_10(8) / log_10(2)

然后你就可以用计算器或者查表来求出这两个对数的值：

log_10(8) ≈ 0.9031

log_10(2) ≈ 0.3010

所以，

log_2(8) = log_10(8) / log_10(2)

≈ 0.9031 / 0.3010

≈ 3

这个结果和直接用指数定义求出来的一样：

log_2(8) = y

⇔

2^y = 8

⇔

y = 3

---

<<<<<<<<c++ 代码实现>>>>>>>>

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    int n;
    long long sum = 0;
    int k;
    long long ans;
    
    cin >> n;
    
    long long a[n];

    for (int i = 0; i < n; i ++)
        cin >> a[i];
    
    sort(a, a + n);
    
    for (int i = 0; i < n; i ++)
        sum += a[i];

    
    k = log(sum)/log(2);
    ans = (long long)pow(2,k);
    cout << ans << endl;
    
    return 0;

}