出题人题解 | #little w and Exchange#

原题解链接：https://ac.nowcoder.com/discuss/150260

先把所有数字按从小到大排序,然后第一个数字必须是$11$ ,如果不是$11$的话首先$11$就凑不出来。

然后下一个面值可以是$11$也可以是$22$ ,但是不可能为$33$,因为如果是$33$或者比$33$还大的话,那么$22$就凑不出来了。

所以得到一个递推的规律:

将数字从小到大排序后,如果下一张纸币的面值$\le sum+1\backslash leq\; sum+1$( $sumsum$为当前纸币的面值 和).那么这张纸币就能放进来更新$sumsum$ ,否则就会断掉导致$sum+1sum+1$无法被构造出来。

最后再判断一下$sumsum$是否大于等于$mm$就可以了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,m;
long long a[100100];
int main()
{
    //freopen("28.in","r",stdin);
    //freopen("28.out","w",stdout);
	while(~scanf("%lld %lld",&n,&m))
	{
		memset(a,0,sizeof(a));
		long long  sum=0;
		int flag=1;
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&a[i]);
		}
		sort(a,a+n);
		sum=a[0];
		if(a[0]!=1)
		{
			flag=0;
		}
		if(a[0]==1)
		{
			for(int i=1;i<n;i++)
			{
				if(sum>=m)
				{
					break;
				}
				if(a[i]>sum+1)
				{
					flag=0;
					break;
				}
				sum+=a[i];
			}
		}
		if(sum<m)
		{
			flag=0;
		}
		if(flag==1)
		printf("YES\n");
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}