hdu 5506

痛定思痛。 2022-08-09 15:52 4阅读 0赞

题意：

有n组数组，每组有若干个数字。

要求将这n组数组划分为L组，每组所有数组的交集不为空。

数据量比较小。

![Center][]

思路 :

一共N个集合, 划分的个数为1…… N个, 所以当 L > N 时必然是不行的

考虑如何取到最小的划分个数cnt, 如果 cnt <= L 则可行

方法 :

记录所有的数出现过的次数

每次都找一个出现次数最多的数, 将存在该数的集合作为一个划分, cnt++, 将该划分中所有集合中的数出现次数都减一, 直到不存在剩余数字为止, 再将cnt与L进行比较

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    const int N=100050;
    typedef long long LL;
    
    int a[305];
    int x[35];
    int num[35][15];
    
    int maxn()
    {
        int m = -1 ;
        int ans = 0 ;
        for(int i = 0 ; i < 305 ; i++)
        {
            if(a[i]>m)
            {
                m=a[i];
                ans = i ;
            }
        }
        return ans;
    }
    
    int main()
    {
        int t,n,ans,l;
        scanf("%d",&t);
        while(t--)
        {
            memset(a,0,sizeof(a));
            memset(x,0,sizeof(x));
            memset(num,0,sizeof(num));
            scanf("%d%d",&n,&l);
            for(int i = 0 ; i < n ; i++)
            {
                scanf("%d",&x[i]);
                for(int j = 0 ; j < x[i] ; j++)
                {
                    scanf("%d",&num[i][j]);
                    a[num[i][j]]++;
                }
            }
            ans = 0 ;
            for(int i = 0 ; i < n ; i++)
            {
    //            for(int h = 0 ; h <= 6 ; h++)
    //            {
    //                cout<<a[h]<<" ";
    //            }
    //            cout<<endl;
                int m = maxn();
                if(m==0)break;
                ans++;
                for(int j = 0 ; j < n ; j++)
                {
                    for(int k = 0 ; k < x[j] ; k++)
                    {
                        if(num[j][k]==m)
                        {
                            for(int p = 0 ; p < x[j] ; p++)
                            {
                                a[num[j][p]]--;
                            }
                            break;
                        }
                    }
                }
            }
            if(ans<=l)printf("YES\n");
            else printf("NO\n");
        }
        return 0 ;
    }

[Center]: /images/20220731/50f4d733295047ec8febb6042ef0d85d.png