啥意思
链接:https://ac.来源:牛客网
题目描述
牛牛喜欢2的幂次,于是他在自己的书包里塞了很多写着2的幂次的卡片
可能多张卡片会写着同一个数字
牛牛喜欢那些能用一张或者多张卡片的和所表示的数字
比如书包里有四张卡片2,4,4,64
那么牛牛就会喜欢10,因为10=2+4+4
也喜欢0
但是不会喜欢12,因为12=4+4+2+2,可怜的牛牛只有一张2
现在牛牛想知道他一共会喜欢多少个数。
输入描述:
第一行输入一个整数n (1 ≤ n ≤ 50),表示卡片的数量
第二行输入n个数,表示每张卡片的数字
每个数字在[1, 2^50]之间
输出描述:
输出一个整数
示例1
输入
复制
2
1 2
输出
复制
4
示例2
输入
复制
4
1 1 1 1
输出
复制
5
示例3
输入
复制
7
1 2 2 2 4 4 16
输出
复制
32
示例4
输入
复制
5
1 32 1 16 32
输出
复制
18
备注:
子任务1:n <= 10
子任务2: n <= 20
子任务3: n <= 50
这道题可以先从小到大排序。可以发现,如果第i个a值不会被前面的值累加得到,说明这个数是和前面的数没有关系,可以把前面的计入答案,否则,需要把cnt+ 这个数除以这个独立集中最小值。
这是别人的思路,看不懂是啥意思
#include<bits/stdc++.h>
using namespace std;
long long n,a[60];
int main()
{
cin>>n;
for(int i=1; i<=n; ++i)
cin>>a[i];
sort(a+1,a+1+n);
a[n+1]=2333333333333333333ll;
long long ans=1,base=0,num=0,Max=0;
for(int i=1; i<=n+1; ++i)
if(Max>=a[i])
{
num+=a[i]/base;
Max+=a[i];
}
else
{
ans*=(num+1);
base=a[i];
Max=a[i];
num=1;
}
cout<<ans<<endl;
return 0;
}
别人的代码