【POJ - 2664】Prerequisites? （排序+查找）

时间：2024-11-19 12:07:14

Prerequisites?

原文是English，这里直接就写中文吧

题意简述

k：已经选择的科目数；m：选择的科目类别；c：能够选择的科目数。r：要求最少选择的科目数量

在输入的k和m以下的一行是选择的科目号。

例：

3 2              　　　　         //3是他选择了3科。2表示选择了两个类别

0123 9876 2222    　    　 //这是他选择的详细的3科科目的科目号

2 1 8888 2222            　    //当中2表示在这个类别里共同拥有两科8888和2222，然后最少要选择这两个中的一个

3 2 9876 2222 7654　　   //这是第二个类别。含义同上。

Sample Input

3 2

0123 9876 2222

2 1 8888 2222

3 2 9876 2222 7654

3 2

0123 9876 2222

2 2 8888 2222

3 2 7654 9876 2222

0

Sample Output

yes

no

题目链接：
https://vjudge.net/problem/POJ-2664

简单题，按照题意模拟一遍即可

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define ll long long

#define INF 0x3f3f3f3f

#define ME0(x) memset(x,0,sizeof(x))

using namespace std;

int k,m,flag;

int a[];

int main()

{

    while(cin>>k,k)

    {

        ME0(a);//每次都初始化数组

        flag=;

        cin >> m;

        for(int i=; i<k; i++)

            cin >> a[i];

        sort(a,a+k);

        for(int i=; i<m; i++)

        {

            int c,r,s;

            s=;

            cin >> c>>r;

            for(int i=; i<c; i++)

            {

                int y;

                cin >> y;

                int t=lower_bound(a,a+k,y)-a;//判断有没有这个数

                if(a[t]==y)

                    s++;

            }

            if(s<r)

                flag=;

        }

        if(flag)

            cout<<"yes"<<endl;

        else

            cout<<"no"<<endl;

    }

    return ;

}
相关文章