题目描述
集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。
本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。
输入格式
输入第一行给出两个正整数：N (≤104) 是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。
随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：
K G[1] G[2] ... G[K]
其中 K (≤1000) 是物品件数，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
Java 代码
如果最后一组数据超时，多提交几次就行。
/*********************************************************************************
Submit Time Status Score Problem Compiler Run Time User
8/30/2019, 20:32:08 Accepted 25 1090 Java (openjdk) 395 ms wowpH
*********************************************************************************/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
// 1、保存不相容的物品，key是物品，list是与key不相容的物品列表
private Map<String, List<String>> incompatibleItems;
public Main() {
// 2、输入流
Reader in = new InputStreamReader(System.in);
BufferedReader input = new BufferedReader(in);
// 3、获取物品对数和清单数量
String[] arr = nextLine(input);
int logarithmofGoods = Integer.parseInt(arr[0]);
int numberofListings = Integer.parseInt(arr[1]);
// 4、创建一个保存不相容物品的哈希映射
incompatibleItems = new HashMap<String, List<String>>();
// 5、输入所有不相容物品，生成不相容物品映射incompatibleItems
for (int i = 0; i < logarithmofGoods; ++i) {
arr = nextLine(input);
addIncompatibleItems(arr[0], arr[1]);
addIncompatibleItems(arr[1], arr[0]);
}
// 7、输入所有清单，检查它是否安全，并输出结果
for (int i = 0; i < numberofListings; ++i) {
arr = nextLine(input);
arr = Arrays.copyOfRange(arr, 1, arr.length);// 1.去掉数组的第一个元素
Arrays.sort(arr);// 2.将清单物品按照编号排序
// 3.检查并输出是否安全
if (checkItems(arr)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// 4、读取一行字符串，转成字符串数组，返回数组
private String[] nextLine(BufferedReader input) {
String[] arr = new String[0];
try {
arr = input.readLine().split(" ");
} catch (IOException e) {
}
return arr;
}
// 6、将incompatibleItem添加到与item不相容的物品列表
private void addIncompatibleItems( String item,
String incompatibleItem) {
List<String> list;
if (incompatibleItems.containsKey(item)) {// 1.包含物品item
list = incompatibleItems.get(item);// 2.获取item的不相容物品列表
} else {// 3.不包含item
list = new ArrayList<String>();// 4.创建新的列表
}
list.add(incompatibleItem);// 5.将incompatibleItem添加到列表中
incompatibleItems.put(item, list);// 6.保存到映射中
}
// 8、检查清单是否安全
private boolean checkItems(String[] itemList) {
for (String item : itemList) {
if (!incompatibleItems.containsKey(item)) {// 1.当前物品无不相容物品
continue;// 2.跳过，检查清单的下一个物品
}
// 3.获取与item不相容的物品列表
List<String> list = incompatibleItems.get(item);
// 4.检查与item不相容的所有物品是否在清单中
for (String inItem : list) {
int index = Arrays.binarySearch(itemList, inItem);
if (index >= 0) {// 5.当前不相容的物品在清单中
return false;// 6.返回不安全
}
}
}
return true;// 7.安全
}
public static void main(String[] args) {
new Main();
}
}
提交结果
