上海计算机学会2021年2月月赛C++丙组T2合成游戏
发布时间
阅读量：
阅读量
合成游戏
内存限制: 256 Mb时间限制: 1000 ms
题目描述
在许多合成类游戏中，通常有这样的玩法：玩家会收到一组数值，并且每个数值均为2的幂次方。在这个系统中，玩家可以选择两个相等大小的数值进行结合生成一个新的数值；这个新数值将是原有数值两倍大小。如果这种操作可以持续进行下去，在给定小爱最初获取的数据集合中，请计算她能够最终达到的最大数值是多少。
2 的幂是指只有 2 作为素因子的正整数。如 4、256 等等。但 60 不是，因为它有素因子 3。
输入格式
第一行：指定的正整数n；
第二行：初始状态下的数字列表为a₁,a₂,…,aₙ，并且每个元素均为2的幂次方。
输出格式
单个正整数：表示最后可以得到的最大数字大小。
数据范围
- 对于 30% 的数据，1≤n≤100，1≤ai≤128；
- 对于 60% 的数据，1≤n≤2000，1≤ai≤2^20；
- 对于 100% 的数据，1≤n≤1,000,000，1≤ai≤2^40；
样例数据
输入:
5
4 1 2 1 1
输出:
8
说明:
两个1合成了一个2，再合成一个4，最后得到8，还有一个1是多余的
解析：
按照题意所述，则若所有数相加后的结果不超过总和，则取其最大值为2的幂次方。具体操作方法是将所有数字相加得到总和后，在不超过该总和的前提下寻找最大的2的幂次方数值作为最终答案。建议使用长整型数据类型进行处理，并参考附录中的代码示例以实现上述逻辑。
#include<bits/stdc++.h>
using namespace std;
long long sum=0;
long long ans;
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
long long t;
scanf("%lld",&t);
sum+=t;
}
ans=1;
while (sum>=ans){
ans*=2;
}
ans/=2;
printf("%lld",ans);
return 0;
}全部评论 (0)
还没有任何评论哟~