1090 危险品装箱 (25分)
集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。
本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。
输入格式：
输入第一行给出两个正整数：N (≤) 是成对的不相容物品的对数；M (≤) 是集装箱货品清单的单数。
随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：
K G[1] G[2] ... G[K]
其中 K (≤) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。
输出格式：
对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。
输入样例：
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
输出样例：
No Yes Yes
总结：这是一道一对多的映射问题
方法一：暴力破解，结构体内数组保存不兼容编号，速度慢
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
struct bu//结构体里的数组储存和下标不兼容的编号
{
vector<int>v;
}buf[100005];
int main()
{
int n,m;
while(cin>>n>>m)
{
int s1, s2;
for (int i = 0; i < n; i++)
{
cin >> s1 >> s2;
buf[s1].v.push_back(s2);//储存不兼容信息
buf[s2].v.push_back(s1);
}
int k;
for (int i = 0; i < m; i++)
{
cin >> k;
vector<int>vk;
int x;
for (int j = 0; j <k; j++)//输入货单
{
cin >> x;
vk.push_back(x);
}
int flag = 0;//flag=0，表示兼容
for (int j = 0; j < k; j++)//从货单的第一号开始，查询它之后的每一个物品单号，是否和它结构体里数组存储的单号有相同的，有flag=1，直接break出循环
{
for (int z = j + 1; z < k; z++)
{
for (int l = 0; l < buf[vk[j]].v.size(); l++)
{
if (vk[z] == buf[vk[j]].v[l])
{
flag = 1;
break;
}
}
if (flag == 1)
break;
}
if (flag == 1)
break;
}
if (flag == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
测试点4的时间 183ms. 2.优化版，创建数组保存输入货单的信息，int a[100000]={0},a[输入的单号]=1，然后遍历buf[输入的单号].v数组，查询a[buf[输入的单号].v数组]是否=1，等于1，不兼容了 #include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
struct bu//结构体里的数组储存和下标不兼容的编号
{
vector<int>v;
}buf[100005];
int main()
{
int n,m;
while(cin>>n>>m)
{
int s1, s2;
for (int i = 0; i < n; i++)
{
cin >> s1 >> s2;
buf[s1].v.push_back(s2);//储存不兼容信息
buf[s2].v.push_back(s1);
}
int k;
for (int i = 0; i < m; i++)
{
cin >> k;
vector<int>vk;
int x;
int a[100000] = { 0 };
for (int j = 0; j <k; j++)//输入货单
{
cin >> x;
vk.push_back(x);
a[x] = 1;
}
int flag = 0;//flag=0，表示兼容
for (int i = 0; i < k; i++)
{
for (int j = 0; j < buf[vk[i]].v.size(); j++)
{
if (a[buf[vk[i]].v[j]] == 1)
{
flag = 1;
break;
}
}
if (flag == 1)
break;
}
if (flag == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
测试点4的时间 85ms 3.map版本，创建map<int,vector<int>>来保存不兼容信息，其中int对应映射的时一个数组
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
int n, k, t1, t2;
map<int,vector<int>> m;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d%d", &t1, &t2);
m[t1].push_back(t2);
m[t2].push_back(t1);
}
while (k--) {
int cnt, flag = 0, a[100000] = {0};
scanf("%d", &cnt);
vector<int> v(cnt);
for (int i = 0; i < cnt; i++) {
scanf("%d", &v[i]);
a[v[i]] = 1;
}
for (int i = 0; i < v.size(); i++)
for (int j = 0; j < m[v[i]].size(); j++)
if (a[m[v[i]][j]] == 1) flag = 1;
printf("%s\n",flag ? "No" :"Yes");
}
return 0;
}
转载自：1090 危险品装箱（25 分）-PAT乙级真题 – 柳婼 の blog
https://www.liuchuo.net/archives/6509 4，multimap版本,多重映射的map
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
int hah[100005];
int arr[1005];
int main(){
int n,m,x,y,t;
multimap<int,int> mp;
mp.clear();
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
mp.insert(pair<int,int>(x,y));
mp.insert(pair<int,int>(y,x));
}
for(int i=0;i<m;i++){
memset(hah,0,sizeof(hah));
multimap<int,int>::iterator it;
scanf("%d",&t);
for(int j=0;j<t;j++){
scanf("%d",arr+j);
hah[arr[j]]=1;
}
int flag=0;
for(int j=0;j<t;j++){
it=mp.find(arr[j]);
if(it!=mp.end()&&hah[it->second]==1){
flag=1;
break;
}
}
if(flag==1) printf("No\n");
else printf("Yes\n");
}
return 0;
}
————————————————
版权声明：本文为CSDN博主「姚军博客」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/SYaoJun/article/details/86644129 5 c语言版的二分查找法
#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;
int list[10000][2] = {{0}}, tmp[1000];
int i, j, f;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++)
scanf("%d %d", &list[i][0], &list[i][1]);//不兼容编号存入二维数组中
for (i = 0; i < m; i++) {
f = 1;
scanf("%d", &k);
for (j = 0; j < k; j++)
scanf("%d", tmp + j);
qsort(tmp, k, sizeof(int), cmp);
for (j = 0; j < n; j++) {
if (bsearch(&list[j][0], tmp, k, sizeof(int), cmp)&& bsearch(&list[j][1], tmp, k, sizeof(int), cmp)) {
puts("No");
f = 0;
break;
}
}
if (f)
puts("Yes");
}
return 0;
}
6 c++版的 binary_search #include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n, m, k;
int i, j, f;
scanf("%d %d", &n, &m);
//vector<vector<int> >list(n,vector<int>(2,0));
int list[10000][2] = {{0}},temp[1000];
for(i = 0; i < n; i++)
scanf("%d %d", &list[i][0], &list[i][1]);
for (i = 0; i < m; i++) {
f = 1;
scanf("%d", &k);
for (j = 0; j < k; j++)
cin>>temp[j];
sort(temp,temp+k);
for (j = 0; j < n; j++) {
if (binary_search(temp,temp+k,list[j][0])&&binary_search(temp,temp+k,list[j][1])) {
cout<<"No"<<endl;
f = 0;
break;
}
}
if (f)
cout<<"Yes"<<endl;
}
return 0;
}
京公网安备 11010502036488号