首页 > 其他分享 >PAT Basic 1090. 危险品装箱

PAT Basic 1090. 危险品装箱

时间：2023-04-13 11:37:34浏览次数：58  
标签：pair1 PAT int next pNode 货品 Basic pair 1090

PAT Basic 1090. 危险品装箱

1. 题目描述：

集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。

本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。

2. 输入格式：

输入第一行给出两个正整数：\(N\) (\(≤10^4\)) 是成对的不相容物品的对数；\(M\) (\(≤100\)) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 \(N\) 行，每行给出一对不相容的物品。第二块有 \(M\) 行，每行给出一箱货物的清单，格式如下：

K G[1] G[2] ... G[K]

其中 K (\(≤1000\)) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

3. 输出格式：

对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。

4. 输入样例：

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

5. 输出样例：

No
Yes
Yes

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

这道题卡了6个小时。。。一开始想着把不相容物品的信息保存在一维数组pair中，这里物品编号用一个5位数表示，所以pair的大小设为\(10^5\)，对于一对不相容物品pair1和pair2，设置pair[pair1]=pair2以及pair[pair2]=pair1。类似之前的派对情侣判断PAT Basic 1065. 单身狗 ，这里进行货品清单判断时，维护check数组保证不相容物品不会同时出现，比如若当前货品为pair1，则设置check[pair[pair1]]=1保证后续货品不能出现pair1的“伴侣”。结果跑测试用例时才发现这里不是一对一的。。。每个货品可以和多个货品不相容。无奈把不相容物品信息改为保存在二维数组pair[10^5][10^5]中，但是这样一个\(10^{10}\)的量级会超出内存限制。。。

最后想到用链表存储每个货品的不相容货品信息，但是经过漫长的修改后testpoint2报Time Limit Exceeded，testpoint3报wrong answer，就这样卡了6个小时。。。无奈搜索此题的C语言题解，找到PAT Basic 1090. 危险品装箱 (C语言实现) - 简书 (jianshu.com) ，是另外一种二分搜索的思路。最后找到PAT Basic 1090 危险品装箱 C语言_pat1090c语言_Allen_0x4bb的博客-CSDN博客 ，同样使用了这种邻接表的思路。看到相同思路是可以AC的，我就决心把bug找出来。。。最后终于发现是因为每一行货品清单判断时，如果出现不相容的货品我会直接break并输出No，但是这一行还有剩余的货品编号留在输入缓冲区中。。。接下来处理下一行货品清单时，会把上一行剩余的货品编号错误输入，就是这么一个trivial的bug卡了我6个小时，加上消耗多余输入的代码后终于AC。

My Code:

// #include <stdio.h>
// #include <string.h> // memset header

// #define MAX_ID 100000

// int main(void)
// {
//     int pairCount=0, orderCount = 0;
//     int pair[MAX_ID] = {0};
//     int i=0, j=0; // iterator
//     int pair1=0, pair2=0;
//     int check[MAX_ID] = {0};
//     int goodsCount=0, tempGoods=0;
    
//     scanf("%d%d", &pairCount, &orderCount);
//     for(i=0; i<pairCount; ++i)
//     {
//         scanf("%d%d", &pair1, &pair2);
//         pair[pair1] = pair2;
//         pair[pair2] = pair1;
        
//         //printf("pair: %d %d\n", pair[pair2], pair[pair1]);
//     }
    
//     for(i=0; i<orderCount; ++i)
//     {
//         //void *memset(void *str, int c, size_t n)
//         // clear the check array
//         memset(check, 0, sizeof(check)); // sizeof (array) will get size of array in byte.
//         scanf("%d", &goodsCount);
//         for(j=0; j<goodsCount; ++j)
//         {
//             scanf("%d", &tempGoods);
//             if(check[tempGoods]) // it's pair already exist
//             {
//                 printf("No\n");
//                 break;
//             }
//             else
//             {
//                 check[pair[tempGoods]] = 1; // set pair of this good to 1
//                 printf("check[%d] = 1\n", pair[tempGoods]);
//             }
//         }
//         if(j==goodsCount)
//         {
//             printf("Yes\n");
//         }
//     }
    
    
//     return 0;
// }


// #include <stdio.h>
// #include <string.h> // memset header

// #define MAX_ID 100000

// // this way cause Segmentation Fault for array size is too big, which reach memory limit
// int main(void)
// {
//     int pairCount=0, orderCount = 0;
//     int pair[MAX_ID][MAX_ID] = {0}; // use 2 dimensional array for every good may have multiple pair
//     int i=0, j=0, k=0; // iterator
//     int pair1=0, pair2=0;
//     int check[MAX_ID] = {0};
//     int goodsCount=0, tempGoods=0;
    
//     scanf("%d%d", &pairCount, &orderCount);
//     for(i=0; i<pairCount; ++i)
//     {
//         scanf("%d%d", &pair1, &pair2);
//         pair[pair1][pair2] = 1;
//         pair[pair2][pair1] = 1;
        
//         //printf("pair: %d %d\n", pair[pair2], pair[pair1]);
//     }
    
//     for(i=0; i<orderCount; ++i)
//     {
//         //void *memset(void *str, int c, size_t n)
//         // clear the check array
//         memset(check, 0, sizeof(check)); // sizeof (array) will get size of array in byte.
//         scanf("%d", &goodsCount);
//         for(j=0; j<goodsCount; ++j)
//         {
//             scanf("%d", &tempGoods);
//             if(check[tempGoods]) // it's pair already exist
//             {
//                 printf("No\n");
//                 break;
//             }
//             else
//             {
//                 for(k=0; k<MAX_ID; ++k)
//                 {
//                     if(pair[tempGoods][k])
//                     {
//                         check[k] = 1; // set pair of this good to 1
//                     }
//                 }
//             }
//         }
//         if(j==goodsCount)
//         {
//             printf("Yes\n");
//         }
//     }
    
    
//     return 0;
// }


#include <stdio.h>
#include <string.h> // memset header
#include <stdlib.h> // malloc header

#define MAX_ID 100000

typedef struct node
{
    int id;
    struct node *next; // remeber this define
} Node;

// first submit testpoint2, 3 wrong answer
// after rectify, testpoint2 Time Limit Exceeded, testpoint3 wrong answer
int main(void)
{
    int pairCount=0, orderCount=0;
    Node pair[MAX_ID];
    int i=0, j=0; // iterator
    int pair1=0, pair2=0;
    //int check[MAX_ID] = {0};
    int goodsCount=0, tempGoods=0;
    Node *pNode = NULL;
    Node *pInsert = NULL;
    
    for(i=0; i<MAX_ID; ++i)
    {
        pair[i].next = NULL;
    }
    
    scanf("%d%d", &pairCount, &orderCount);
    for(i=0; i<pairCount; ++i)
    {
        scanf("%d%d", &pair1, &pair2);
        
        pNode = &pair[pair1];
        pInsert = (Node *)malloc(sizeof(Node));
        pInsert->id = pair2;
        pInsert->next = pNode->next;
        pNode->next = pInsert;
 
        pNode = &pair[pair2];
        pInsert = (Node *)malloc(sizeof(Node));
        pInsert->id = pair1;
        pInsert->next = pNode->next;
        pNode->next = pInsert;
        
//         scanf("%d%d", &pair1, &pair2);
//         pNode = &pair[pair1];
//         while(pNode->next != NULL) pNode = pNode->next; //++pNode;
//         pNode->next = (Node *)malloc(sizeof(Node));
//         pNode = pNode->next;
//         pNode-> id = pair2;
//         pNode-> next = NULL;
        
//         pNode = &pair[pair2];
//         while(pNode->next != NULL) pNode = pNode->next; //++pNode;
//         pNode->next = (Node *)malloc(sizeof(Node));
//         pNode = pNode->next;
//         pNode-> id = pair1;
//         pNode-> next = NULL;
    }
    
//     for(i=0; i<MAX_ID; ++i) // output pair info
//     {
//         pNode = &pair[i];
//         if(pNode->next)
//         {
//             pNode = pNode->next;
//             printf("%d:", i);
//             while(pNode)
//             {
//                 printf(" %d", pNode->id);
//                 pNode = pNode->next;
//             }
//             printf("\n");
//         }
//     }
    
    for(i=0; i<orderCount; ++i)
    {
        int check[MAX_ID] = {0};
        //void *memset(void *str, int c, size_t n)
        // clear the check array
        //memset(check, 0, sizeof(check)); // sizeof (array) will get size of array in byte.
        //printf("sizeof Check: %zd\n", sizeof(check));
//         for(j=0; j<MAX_ID; ++j)
//         {
//             if(check[j])
//             {
//                 printf("%d ", check[j]);
//             }
//         }
//         printf("\n");
        
        // here directly break will cause inputs of every line stay in istream!!!
        // is really a trivial bug!!!
        scanf("%d", &goodsCount);
        for(j=0; j<goodsCount; ++j)
        {
            scanf("%d", &tempGoods);
            if(check[tempGoods]) // it's pair already exist
            {
                printf("No\n");
                //printf("can't have: %d\n", tempGoods);
                break;
            }
            
            pNode = &pair[tempGoods];
            pNode = pNode->next;
            // this fixed Segmentation Fault
            while(pNode != NULL) //(pNode->next != NULL), this will cause Segmentation Fault when pNode is already NULL
            {
                check[pNode->id] = 1; // set pair of this good to 1
                pNode = pNode->next;
            }
            
        }
        if(j==goodsCount)
        {
            printf("Yes\n");
        }
        
        for(++j; j<goodsCount; ++j) // consume remain input
        {
            scanf("%d", &tempGoods);
        }
//         for(j=1; j<MAX_ID; ++j)
//         {
//             if(check[j])
//             {
//                 printf(" %d", j);
//             }
//         }
//         printf("\n");
        
    }
    
    
    return 0;
}


// // refer to https://www.jianshu.com/p/c1de41aebf62
// #include <stdio.h>
// #include <stdlib.h>

// int cmp(const void *a, const void *b)
// {
//     return *(int*)a - *(int*)b;
// }

// int main()
// {
//     int N, M, K, status;
//     int itemlist[1000], pairlist[10000][2] = {{0}};

//     /* Record incompatible list */
//     scanf("%d %d", &N, &M);
//     for(int i = 0; i < N; i ++)
//         scanf("%d %d", &pairlist[i][0], &pairlist[i][1]);

//     for(int i = 0; i < M; i++)
//     {
//         status = 1;
//         scanf("%d", &K);
//         for(int j = 0; j < K && status; j++)
//             scanf("%d", itemlist + j);

//         qsort(itemlist, K, sizeof(int), cmp);

//         for(int j = 0; j < N; j++)
//         {
//             if(bsearch(&pairlist[j][0], itemlist, K, sizeof(int), cmp)
//             && bsearch(&pairlist[j][1], itemlist, K, sizeof(int), cmp))
//             {
//                 puts("No");
//                 status = 0;
//                 break;
//             }
//         }

//         if(status)
//             puts("Yes");
//     }

//     return 0;
// }

标签：pair1,PAT,int,next,pNode,货品,Basic,pair,1090
From： https://www.cnblogs.com/tacticKing/p/17312821.html

相关文章

  • PathView实现炫酷SVG动画
    解析SVG,需要将一个androidsvg.jar包含进libshttps://github.com/geftimov/android-pathview<?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="http://schemas.android.com/apk/res/android"android:orientati......
  • springboot 中的 classpath 指的是什么路径？
    classpath其本质其实是指项目打包后的classes下的路径，一般用来指代“src/main/resources”下的资源路径。通常会在各种配置文件中使用【classpath】关键字，例如：yml配置文件：WebMvcConfigurer配置类：......
  • PAT-basic-1028 人口普查 java c++
    一、题目某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过200岁的老人，而今天是2014年9月6日，所以超过200岁的生日和未出生的生日都是不合理的，应该被过......
  • PAT-basic-1029 旧键盘 java c++
    一、题目旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。输入格式：输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括......
  • PAT Basic 1089. 狼人杀-简单版
    PATBasic1089.狼人杀-简单版1.题目描述：以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1号玩家说：“2号是狼人”，2号玩家说：“3号是好人”，3号玩家说：“4号是狼人”，4号玩家说：“5号是好人”，5号玩家说：“4号是好人”......
  • PAT Basic 1088. 三人行
    PATBasic1088.三人行1.题目描述：子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是2位正整数；把甲的能力值的2个数字调换位置就是乙的能力值；甲乙两人能力差是丙的能力值的X倍；乙的能力值是丙的Y倍。......
  • xpath数据解析
    xpath解析xpath是一种在XML文档中査找信息的语言，可用来在XML文档中対元素和属性进行遍万。HTML属于XML的一个子集。1、导入fromlxmlimportetree#如果导入报错，则使用以下方式fromlxmlimporthtmletree=html.etree2、创建xpath对象#解析XML文件et=etree.XML......
  • PAT Basic 1087. 有多少不同的值
    PATBasic1087.有多少不同的值1.题目描述：当自然数 \(n\) 依次取\(1、2、3、……、N\) 时，算式 \(⌊n/2⌋+⌊n/3⌋+⌊n/5⌋\) 有多少个不同的值？（注：\(⌊x⌋\) 为取整函数，表示不超过 \(x\) 的最大自然数，即 \(x\) 的整数部分。）2.输入格式：输入给出一个正整数 \(N\)（\(......
  • PAT Basic 1086. 就不告诉你
    PATBasic1086.就不告诉你1.题目描述：做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着输出它们的乘积。2.输入格式：输入在第一行给出两个不超过1000的正整数A和B，其间以空格分隔。......
  • pytest中的monkeypatch
    一、猴子补丁简介在有些场景下的测试可能需要修改全局配置或者系统变量等操作，而这些操作仅仅是为了做一些测试，不希望永久的修改，此时就需要使用猴子补丁了，猴子补丁，即monkeypatch，是一个fixture，它提供了以下方法：monkeypatch.setattr(obj,name,value,raising=True)monkeypatch.se......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99