Message Flood
总提交:341 测试通过:91
描述
Well, how do you feel about mobile phone? Your answer would probably be something like that “It’s so convenient and benefits people a lot”. However , if you ask Merlin this question on
the New Year’s Eve , he will definitely answer “ What a trouble! I have to keep my fingers moving on the phone the whole night , because I have so many greeting messages to send !” . Yes , Merlin has such a long name list of his friends , and he would like
to send a greeting message to each of them . What’s worse , Merlin has another long name list of senders that have sent message to him , and he doesn’t want to send another message to bother them ( Merlin is so polite that he always replies each message he
receives immediately ). So , before he begins to send messages , he needs to figure to how many friends are left to be sent . Please write a program to help him.
Here is something that you should note. First , Merlin’s friend list is not ordered , and each name is alphabetic strings and case insensitive . These names are guaranteed to be not duplicated . Second, some senders may send more than one message to Merlin
, therefore the sender list may be duplicated . Third , Merlin is known by so many people , that’s why some message senders are even not included in his friend list.
输入
There are multiple test cases . In each case , at the first line there are two numbers n and m ( 1<=n , m<=20000) , which is the number of friends and the number of messages he has received . And
then there are n lines of alphabetic strings ( the length of each will be less than 10 ) , indicating the names of Merlin’s friends , one pre line . After that there are m lines of alphabetic string s ,which are the names of message senders .
The input is terminated by n=0.
输出
For each case , print one integer in one line which indicates the number of left friends he must send .
样例输入
5 3
Inkfish
Henry
Carp
Max
Jericho
Carp
Max
Carp
0
样例输出
3
题目来源
第九届中山大学程序设计竞赛预选题
(容器)代码:
#include<iostream> #include<set> #include<string> using namespace std; int main() { string str; int m,n; while(cin>>n&&n) { set<string> myset; cin>>m; for(int i=0;i<n;i++) { cin>>str; for(int j=0;j<str.length();j++) str[j]=tolower(str[j]); myset.insert(str); } for(int i=0;i<m;i++) { cin>>str; for(int j=0;j<str.length();j++) str[j]=tolower(str[j]); set<string>::iterator itor=myset.find(str); if(itor!=myset.end()) myset.erase(str); } cout<<myset.size()<<endl; } return 0; }
代码:
#include <iostream> #include <string> #include <algorithm>//algorithm,用cmp和sort函数时要添加的头文件 #include <memory.h>//用memset时要添加的头文件 using namespace std; bool cmp(string a, string b) { return a < b; //这个是增序 } string name[20001], tmp; //都是全局变量了 bool found[20001]; int n, m; bool bi_search(); int main() { int i,count; while (cin >> n && n) //这句话特别有用,要会使用 { cin >> m; memset(found, false, 20001*sizeof(bool));// 没有了这句话会有wrong answer for (i = 0; i < n; i++) { cin >> name[i]; for (int j = 0; j < name[i].length(); j++) name[i][j] = tolower(name[i][j]); //将大写字母转化成小写字母 } count = n; sort(name, name+n, cmp);//注意使用方法 for (i = 0; i < m; i++) { cin >> tmp; for (int j = 0; j < tmp.length(); j++) tmp[j] = tolower(tmp[j]); if (bi_search()) count--; } cout << count << endl; } return 0; } bool bi_search()//这个二分法写得很好,适当记下 { int start = 0, mid, end = n-1; while (start <= end) { mid = (start+end)/2; if (tmp == name[mid]) { if (!found[mid]) { found[mid] = true; return true; } else return false; } else if (tmp < name[mid]) end = mid-1; else start = mid+1; } return false; }