本文主要是介绍1731 圣诞节礼物,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
圣诞节快到了,Jimmy 买了好多礼物准备送给他的朋友们,他想把价格为 S1 的礼物送给第 1 个朋友,价格为 S2的礼物送给第 2 个朋友.....以此类推,他想把价格为 Si 的礼物送给第 i 个朋友。但是他买的礼物太多了,以至于他忘了是否存在价格为 Si 的礼物。幸运的是 Jimmy 把购物清单留了下来 。
现在告诉你 Jimmy 购买的 n 件礼物的价格,以及他想要送的 m 件礼物的价格,他想知道他能否从买的 n 件礼物中挑出那 m 件送给他的朋友们。如果能的话就告诉他“YES”, 否则告诉他“NO”。
输入包含多组数据。
对于每组数据,第一行为两个正整数 n 和 m (0 < n , m <= 100000),分别为买的礼物的件数和想要送的礼物件数。第二行 n 个正整数,为买的 n 件礼物的价格。第三行 m 个正整数,第 i 个数代表想要送给第 i 个朋友的礼物的价格。(价格都在231以内)
当 n = m = 0 时输入结束。
每一组数据输出一行,如果能则输出“YES”,否则输出“NO”。
解题思路:首先需要针对礼物的价格和送给朋友的礼物价格进行排序,然后两个数组从头开始查找,遇到礼物价格比送的价格小,就继续查找,直到礼物价格查找到头,如果此时仍然无法满足,则表明无法实现任务。
#include <iostream>
#include <algorithm>
using namespace std;
int a[100002],b[100002];
class compare
{
public:
bool operator()(const int &x,const int &y)
{
return x<y;
};
};
int main()
{
int n,m;
int i,j;
compare cmp;
cin>>n>>m;
while(!(n==0&&m==0))
{
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,cmp);
for( j=0;j<m;j++)
cin>>b[j];
sort(b,b+m,cmp);
for (j=i=0; j<m; j++,i++)
{
while (i<n && a[i]<b[j])
i++;
if (i>=n || a[i]>b[j])
break;
}
if (j>=m)
cout << "YES" << endl;
else
cout << "NO" << endl;
cin>>n>>m;
}
return 0;
}
这篇关于1731 圣诞节礼物的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!