题目描述 寻宝人听说在一座古老的森林中有隐藏的宝藏。他准备在夜晚进行一次秘密行动,找到并将宝藏运出森林。
历经千难万险,他终于找到了宝藏。但他发现,这不是普通的宝藏,而是被施过魔法的宝藏。
经过反复尝试,他发现,如果用带来的背包来装这些宝藏,一旦装入背包的宝藏的重量求和的过程中产生了进位,装入背包的宝藏会自动全部消失。
发现了这个规律之后,寻宝人清点了剩余的宝藏一共还有 N N 件,并统计了每件宝藏的重量。
请编程帮助寻宝人求出,他最多能带多少件宝藏,离开森林。
输入格式 第 1 1 行读入整数 N N,代表还有 N N 件宝藏。
接下来 N N 行,每行读入一个整数,代表了每件宝藏的重量。
输出格式 输出寻宝人最多能带走的宝藏数量。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25;
ll n,sum,ans;
ll a[N];
ll cnt;
bool cmp(ll a,ll b)
{
ll x=a,y=b;
while(x && y)
{
if(x%10<y%10) return true;
else if(x%10>y%10) return false;
x/=10;
y/=10;
}
return x>y;
}
bool cnp(ll a,ll b)
{
ll x=a,y=b;
while(x && y)
{
if(x%10+y%10>=10) return false;
x/=10;
y/=10;
}
return true;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
ans=1;
sum=a[1];
for(int i=2;i<=n;i++)
{
while(cnp(sum,a[i]) && i<=n)
{
ans++;
sum+=a[i];
i++;
}
}
cout<<ans;
return 0;
}