[数组计数法]#116. 开会时间

题目描述

一年一度的信息学奥林匹克总结大会准备召开了，但大会负责人Mr.Huang却遇到了麻烦，参加会议的各中小学信息学教练都非常非常忙，因为他们不但要担任竞赛的辅导工作，而且还有常规的教学工作，有的还担任学校的行政职务，因此要召集他们都来开会是一件非常困难的事，为了让更多的人来参加会议，时间的选择非常关键。因此Mr.Huang让他们每个人交一份空闲时间表（单位：天），他们也只能在空闲的时间才能来开会。Mr.Huang请你通过他们提供的空闲时间表来确定开会的时间（会开一整天）。自然是能来的人越多越好，在这个前提下，请你确定某一天开会，如何能来的人数相同的话，会越早开越好，当然如何与会人数小于组委会设定的最少人数，会议将被取消。

输入格式

第一行为两个正整数N，Q（1 ≤ Q ≤ N ≤ 50），其中 N 表示信息学教练的总人数，Q 表示至少需要多少信息学教练参加，使得会议能够召开。

接下来有N 行，每行有若干个整数。第一个整数是 K，表示第 i 个人有 K 天空闲，紧接着有 K 个整数 ki（ki ≤ 100），表示他第 ki 天空闲。

输出格式

只有一个整数，为开会的最早时间，如果与会人数少于组委会设定的人数Q，会议被取消，则输出“0”。

样例输入/输出

输入数据 1

3 2             
4 1 5 8 9       
3 2 5 9
5 2 4 5 7 9

输出数据 1

5

数据规模与提示

样例一说明：

第一行，3 表示总人数，2 表示至少需要 2 人，使得会议可以召开；

第二行，表示第一个人有4 天有空，分别是第 1 天、第 5 天、第 8 天、第 9 天有空闲；后面几行同上。

输出5 表示会议最早在第 5 天召开。

时间限制：1s.

内存限制：1m.

做题！！！

该问题可以使用数组计数法来解决。

首先，我们可以创建一个大小为101的数组count，用于记录每一天有多少人有空闲。然后，我们遍历每个教练的空闲时间表，将对应的天数在count数组中加1。

接下来，我们从第1天开始，依次判断每一天是否满足开会的条件。如果count[i] >= Q，表示在第i天有至少Q个教练有空闲，则输出i并结束程序。如果遍历完所有的天数都没有找到满足条件的开会时间，则输出0表示会议无法召开。

以下是示例代码的实现：

#include<bits/stdc++.h>
using namespace std;
long long a,b,k,e[1000000+250];
int main()
{
cin>>a>>b;
    for(int i=1;i<=a;i++)
    {
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            long long x;
            cin>>x;
            e[x]++;
        }
    }
    long long zd=0,zdi=0;
    for(int i=1;i<=100;i++)
    {
        if(e[i]>zd)
        {
            zd=e[i];
            zdi=i;
        }
    }
    if(zd<b)
        cout<<0;
    else
        cout<<zdi;
    return 0;
}

样例输入1解释：
第一行，3 表示总人数，2 表示至少需要2人，使得会议可以召开；
第二行，表示第一个人有4天有空，分别是第1天、第5天、第8天、第9天有空闲；后面几行同上。

输出5表示会议最早在第5天召开。

点个赞吧，帅哥美女们，本人为小学生。

原文地址：https://blog.csdn.net/gcliyilin/article/details/142419797

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！