PAT甲级1149Dangerous Goods Packaging

Posted on | | Visitors:
Words count in article: 1,032 字 | Reading time ≈ 5 分

题目链接

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

题目要求

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

  • 输入

    • N：不能装在一起的货物对的数量，不超过10000

    • M：要运输的货物的组数，不超过100

    • N组不能装在一起的货物：每组包括两个货物索引

    • M组货物

      第一个数字K（不超过1000）是货物的数量，然后剩下的是货物索引（5位数字）

  • 输出

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

题解一

思路

这个思路会超时

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 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\n");
        else
            printf("No\n");        
    }

    return 0;
}

题解二

思路

  1. 使用邻接表保存每个货物的不能装在一起的货物

  2. 对于每组货物，使用一维数组保存每个货物是否在这组货物中

  3. 查询邻接表，并通过一维数组判断每个货物的不相容货物是否出现在这组货物中

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 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\n");
        else
            printf("No\n");
    }

    return 0;
}

参考链接

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

作者：@臭咸鱼

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

欢迎讨论和交流!