[牛客] 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;
} ```
