PAT甲级1149Dangerous Goods Packaging

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/1038429908921778176

题目要求

当用容器运输货物时，一些货物是不能装在一起的。现在告诉你哪些货物能装在一起，给你一些货物，请判断这些货物是否可以被装在一起

输入
- N：不能装在一起的货物对的数量，不超过10000
- M：要运输的货物的组数，不超过100
- N组不能装在一起的货物：每组包括两个货物索引
- M组货物
  
  第一个数字K（不超过1000）是货物的数量，然后剩下的是货物索引（5位数字）
输出

对于M组货物中的每组，如果其中没有不可以装在一起的货物则输出Yes，否则输出No

题解一

思路

这个思路会超时

通过map和hash记录两个货物是否可以被装在一起，相当于一个邻接矩阵
- 为什么不定义矩阵？如果要用矩阵，在这里就需要定义一个100000×100000的bool矩阵，大概会占用10GB，而内存限制是64MB。
对于每组货物，两两判断是否不相容，是一个两层循环，时间复杂度是(K^2)，再算上M组查询，时间复杂度就是(MK^2)，最大值为100×1000×1000=1e8，大概会耗时1秒，肯定会超过400ms的时间限制。

代码

// Problem: PAT Advanced 1149
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1038429908921778176
// Tags: Graph Map Hash

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    int n, m, k;
    scanf("%d %d", &n, &m);

    int good1, good2;
    unordered_map<int, bool> incompatible; // 通过map和hash记录两个货物是否可以被装在一起
    
    while (n--){ // 通过map和hash记录两个货物是否可以被装在一起
        scanf("%d %d", &good1, &good2);
        incompatible[good1 * 100000 + good2] = true;
        incompatible[good2 * 100000 + good1] = true;
    }

    while (m--){ //判断m组货物
        scanf("%d", &k);
        vector<int> goods(k);
        for (int i = 0; i < k; i++) // 记录k个货物
            scanf("%d", &goods[i]);
        
        bool isYes = true;
        for(int i = 0; i < k - 1; i++){ //判断k个货物是否可以放在一起
            good1 = goods[i];
            for (int j = i + 1; j < k; j++){
                good2 = goods[j];
                if (incompatible[good1 * 100000 + good2] || incompatible[good2 * 100000 + good1]){
                    isYes = false;
                    break;
                }
            }
        }

        // 输出结果
        if (isYes)
            printf("Yes
");
        else
            printf("No
");        
    }

    return 0;
}

题解二

思路

使用邻接表保存每个货物的不能装在一起的货物
对于每组货物，使用一维数组保存每个货物是否在这组货物中
查询邻接表，并通过一维数组判断每个货物的不相容货物是否出现在这组货物中

这里也是用了两层循环，但这两层循环的时间复杂度是(N)，再算上M组查询，时间复杂度就是(MN)，最大值为100×10000=1e6。

代码

// Problem: PAT Advanced 1149
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1038429908921778176
// Tags: Graph Map Hash

#include <iostream>
#include <vector>
using namespace std;

vector<int> incompatible[100000]; // 邻接表，货物与哪些货物不能装在一起

int main()
{
    int n, m, k, good1, good2;
    scanf("%d %d", &n, &m);
    while (n--){  // 建立邻接表
        scanf("%d %d", &good1, &good2);
        incompatible[good1].push_back(good2);
        incompatible[good2].push_back(good1);
    }

    while (m--){ // m组货物
        scanf("%d", &k);
        vector<int> goods(k); // 该组货物
        bool contained[100000]={false}; // 该组货物中有哪些货物
        for (int i = 0; i < k; i++){ // 记录该组货物
            scanf("%d", &goods[i]);
            contained[goods[i]] = true;
        }

        bool isYes = true;
        for (int i = 0; i < k; i++){ // 查询邻接表，并通过一维数组判断每个货物的不相容货物是否出现在这组货物中
            for (int j = 0; j < incompatible[goods[i]].size(); j++){
                if (contained[incompatible[goods[i]][j]]){
                    isYes = false;
                    break;
                }
            }
        }

        // 输出结果
        if (isYes)
            printf("Yes
");
        else
            printf("No
");
    }

    return 0;
}

参考链接

https://blog.csdn.net/liuchuo/article/details/82560836

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!