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;
// }