[牛客] little w and Exchange

登录—专业IT笔试面试备考平台_牛客网

https://ac.nowcoder.com/acm/contest/297/D

[题目链接](https://ac.nowcoder.com/acm/contest/297/D)

------------
定义有n张纸币,且存在m,使得这n张纸币可以通过任意组合构成不超过m元的任意值,则n符合
用a[n+1]表示第n+1张纸币的值,当a[n+1] <= m+1 时n+1才符合
证明:
反证法:若a[n+1] > m+1,那么无论n+1张纸币如何组合,都无法构成m+1元
注意:计算前要将a[n]进行从小到大排序
------------
代码
 #include <bits/stdc++.h>
using namespace std;
#define mset(var,val) memset(var,val,sizeof(var))
#define lowbit(x) (x&-x)
#define ls(i) i<<1
#define rs(i) i<<1|1
typedef long long int lli;
typedef unsigned long long ull;
const ull base=131;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const long double eps=1e-20;
const int mod=1e9+7;
const int M=10010;
int main(int argc, char const *argv[])
{
 int n,m,a[M];
 scanf("%d%d",&n,&m);
 for(int i=0;i<n;i++)
  scanf("%d",&a[i]);
 sort(a,a+n);
 int now=0;
 for(int i=0;i<n;i++)
  if(a[i]<=now+1)now+=a[i];
  else break;
 if(now>=m)cout<<YES<<endl;
 else cout<<NO<<endl;
}
```

全部评论

相关推荐

预计下个星期就能开奖吧,哪位老哥来给个准信
华孝子爱信等:对接人上周说的是这周
点赞 评论 收藏
分享
吃不饱的肱二头肌很想退休:tnnd 我以为选妹子呢,亏我兴高采烈的冲进来😠
投递快手等公司10个岗位
点赞 评论 收藏
分享
头像
09-29 16:18
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 10:52
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务