PAT甲级——1121 Damn Single (C++的各种stl的使用)

"Damn Single (单身狗)" is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID's which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (≤ 10,000) followed by M ID's of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.

Output Specification:

First print in a line the total number of lonely guests. Then in the next line, print their ID's in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

Sample Output:

5
10000 23333 44444 55555 88888

题目大意:给出N对情侣,然后在M个客人中找出单身狗并且按照名字的字母升序排列输出。。。  

思路:用unordered_map存储每对情侣,用unordered_set存储客人信息,遍历客人的集合,如果当前的ID没有对象或者他的对象没有参加party,那么就属于单身狗。(另一半没来的也是单身狗!!!)

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
unordered_map <string, string> cp;
unordered_set <string> guest;
bool isSingle(string ID);
int main()
{
	int N, M, i;
	vector <string> ans;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		string v, u;
		cin >> v >> u;
		cp[v] = u;
		cp[u] = v;
	}
	scanf("%d", &M);
	for (i = 0; i < M; i++) {
		string ID;
		cin >> ID;
		guest.insert(ID);
	}
	for (auto it = guest.begin(); it != guest.end(); it++) 
		if (isSingle(*it)) 
			ans.push_back(*it);
	sort(ans.begin(), ans.end());
	printf("%d\n", ans.size());
	for (i = 0; i < ans.size(); i++) {
		printf("%s", ans[i].c_str());
		if (i < ans.size() - 1)
			printf(" ");
	}
}
bool isSingle(string ID) {
	if (guest.find(cp[ID]) == guest.end()) 
		return true;
	else
		return false;
}

 

上一篇:镜像制作


下一篇:Java 12 Teeing Collector