青岛市崂山区建设局网站,wordpress默认首页设置,泉州seo按天收费,用discuz做行业网站题干#xff1a;
旅行到K国的小w发现K国有着很多物美价廉的商品#xff0c;他想要买一些商品。
结果一掏钱包#xff0c;包里只剩下n张K国的纸币了#xff0c;说起来也奇怪#xff0c;K国纸币并不像其他国家一样都是1元#xff0c;5元#xff0c;10元…而是各种奇怪的…题干
旅行到K国的小w发现K国有着很多物美价廉的商品他想要买一些商品。
结果一掏钱包包里只剩下n张K国的纸币了说起来也奇怪K国纸币并不像其他国家一样都是1元5元10元…而是各种奇怪的面值所以找零就不是很方便。
已知商店里的商品价格都是小于等于m的正整数如果有可能存在某个商品的价格为xm并且x无法在不找零的情况下支付小w就不能任意购买一件商店中的商品小w想知道自己在不找零的情况下能否任意购买一件商店中的商品你能帮帮他么
输入描述:
第一行是两个正整数n,mn1000,m2^31-1
第二行共n个正整数ai(1ai2^31-1)代表小w钱包中K国纸币的面值。
输出描述:
如果能任意购买商店中的物品请输出YES(不含引号)。
如不能任意购买商店中的物品请输出NO不含引号。
示例1
输入
复制
4 10
1 2 3 4
输出
复制
YES
说明
小w可以用面值为1的纸币在不找零的情况下购买价值为1的商品
小w可以用面值为2的纸币在不找零的情况下购买价值为2的商品
小w可以用面值为1、2的纸币在不找零的情况下购买价值为3的商品
小w可以用面值为4的纸币在不找零的情况下购买价值为4的商品
小w可以用面值为1、4的纸币在不找零的情况下购买价值为5的商品
小w可以用面值为2、4的纸币在不找零的情况下购买价值为6的商品
小w可以用面值为1、2、4的纸币在不找零的情况下购买价值为7的商品
小w可以用面值为1、3、4的纸币在不找零的情况下购买价值为8的商品
小w可以用面值为2、3、4的纸币在不找零的情况下购买价值为9的商品
小w可以用面值为1、2、3、4的纸币在不找零的情况下购买价值为10的商品
示例2
输入
复制
4 10
5 5 2 1
输出
复制
NO
说明
小w可以用面值为1的纸币在不找零的情况下购买价值为1的商品
小w可以用面值为2的纸币在不找零的情况下购买价值为2的商品
小w可以用面值为1、2的纸币在不找零的情况下购买价值为3的商品
小w无法在不找零的情况下用手中的纸币构造出价值为4的商品的购买方案所以认为小w无法任意购买商店中的商品
备注:
纸币的面值可能会相同每张纸币仅有一张可以使用或者不使用。当且仅当你能用手里的纸币凑出价值恰好为1,2,3,4,5,....m的物品的购买方案时我们认为可以任意购买物品。你可以认为这m个查询都是独立的。也就是说同一张纸币可以在购买不同价值的物品方案中出现。 解题报告 不难证明cur是代表你当前可以凑出1~cur所有的值贪心就出答案了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll n,m;
ll a[MAX];
int main()
{cinnm;for(int i 1; in; i) scanf(%lld,ai);sort(a1,an1);ll cur 0;for(int i 1; in; i) {if(a[i] cur1) {cura[i];}else break;}if(cur m) puts(YES);else puts(NO);return 0 ;}
