圣诞节礼物
时间限制：1000 ms  |  内存限制：65536 KB
描述
圣诞节快到了，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”。


样例输入
10 4
1 2 3 4 5 6 7 8 9 10
2 3 5 90
10 3
1 2 3 4 5 78 33 22 2 1
2 2 4
0 0
样例输出
NO
YES

题目连接http://www.

[ 本帖最后由 laoyang103 于 2011-9-17 11:13 编辑 ]

#include <stdio.h>
int main()
{
    int i,j,k;
    int m,n,v;
    while(scanf("%d%d",&n,&m) && (m||n))
    {
        int a[100000] = {0};
        for(i = 0;i<n;i++)
        {
            scanf("%d",&v);
            a[v]++;
        }
        for(i = 0;i<m;i++)
        {
            scanf("%d",&v);
            if(a[v])
                a[v]--;
            else
                break;
        }
        if(i == m)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

这是我代码  直接用的哈希表 时间复杂度位m+n怎么就超时

[ 本帖最后由 laoyang103 于 2011-9-17 10:40 编辑 ]

#include <stdio.h>
#include <stdlib.h>
int cmp(const void *pa,const void *pb)
{
    return *(int *)pa - *(int *)pb;
}
int main()
{   
    int m,n;
    while(scanf("%d%d",&n,&m) && (m||n))
    {       
        int i,j;
        int a[100005] = {0};
        int b[100005] = {0};
        for(i = 0;i<n;i++)
            scanf("%d",&a[i]);
        for(i = 0;i<m;i++)
            scanf("%d",&b[i]);
        qsort(a,n,4,cmp);
        qsort(b,m,4,cmp);
        i = j = 0;
        while(i<m && j<n)
        {
            if(b[i]<a[j])
                break;
            else if(b[i]>a[j])
                j++;
            else
            {i++;j++;}
        }
        if(i == m)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

对于这个题我表示很纠结  总结一下 发这个帖子的原因是 因为我看错了题 题目说是数据个数位100000 而不是数据范围

所以错误的开了100000的散列表 这样数组肯定越界 但是给我的提示是超时 是我想不到是因为越界 浪费了一天时间

还有是最后提交的几次答案错误是因为我把YES 写成了 Yes 我的代码很垃圾但是能过 这个题楼上用了50多MS希望他能把代码贡献一下