试题 算法训练 预备爷的悲剧

题目

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

英语预备爷gzp是个逗(tu)比(hao)，为了在即将到来的英语的quiz中不挂科，gzp废寝忘食复习英语附录单词表，俨然一场人间悲剧。不过上天有好生之德，上帝扔给了gzp一张纸，上面记载了将要考到的单词。不过gzp是个逗比，之前复习的东西全忘记了，所以他又要再来一次复习。不过已经知道了要考的单词，所以不需要复习单词表的所有页数。因此，现在需要你帮助他求出有多少页纸需要复习。他会告诉你每个单词会在哪几页出现，并且告诉你要考哪些单词，你只要告诉他答案就可以了。由于一个单词会出现在不同页上，只需要复习在最前面一页上的就可以了。

输入格式

第一行一个整数n，表示单词附录有n个单词。接下来n行每行一个小写字母组成的单词和一个整数，表示某一个单词和它所在的页数。接下来是一行整数m，表示要考m个单词，接下来m行小写字母组成的单词，表示要考到的单词。

输出格式

一个数，表示需要复习的页数。

样例输入

5
ab 1
ac 2
ab 2
ac 3
c 3
3
ab
ac
c

样例输出

3

数据规模和约定

0<=n,m<=100000，单词长度<=10。

很容易就想到用map了吧

值得注意的是，由于一个单词会出现在不同页上，只需要复习在最前面一页上的就可以了。，这一句话，即如果相同的单词出现了多次，只复习出现在最前面那一页的，比如ab 2， ab 3， ab 1，如果要复习ab，只需要复习第一页就行了。

1.map代码

思路：对于每个单词，我们只存它最靠前的页数

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
//换个简短的
typedef map<string, int>::iterator MyIt;

int main()
{
    //单词
	map<string, int> words;
    //要复习的页数
	set<int> pages;
	int n;
	cin >> n;
	for ( int i = 0; i< n; ++i ) {
		string s;
		int num;
		cin >> s >> num;//输入单词和页数
		if ( words.count(s) == 0 ) { //如果words中没有，就直接插入进去
			words[s] = num;
		}
		else {//单词s已经出现过了，
			MyIt it = words.find(s);
            /*
            我们只存出现页面最靠前的！！！！
            */
			if ( it->second > num ) {
				words[s] = num;
			}
		}
	}
	int m;
	cin >> m;
	for ( int i = 0; i < m; ++i ) {
		string s;
		cin >> s;
		MyIt it = words.find(s);
		pages.insert(it->second);
	}
	cout << pages.size() << endl;
	return 0;
}

multimap来做：

这个是允许重复的key出现的，即key可以在multimap中重复出现，并且并且并且，重复出现的key是相邻的位置的，但是她就不支持 [] 运算符了，所以用insert来插入

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef multimap<string, int>::iterator MyIt;
int main()
{
	multimap<string,int> words;
	words.insert(make_pair("ab",1));
	words.insert(make_pair("cc",1));
	words.insert(make_pair("dd",1));
	words.insert(make_pair("cc",1));
	words.insert(make_pair("ab",1));
	for ( auto temp : words ) {
		cout << temp.first << "->" << temp.second << endl;
	}
	return 0;
}

又因为find找的是首次出现的，所以就可以通过遍历来找到单词出现的最小页数了。

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef multimap<string, int>::iterator MyIt;

int main()
{
	multimap<string, int> words;
	set<int> pages;
	int n;
	cin >> n;
    //全部存进去
	for ( int i = 0; i< n; ++i ) {
		string s;
		int p;
		cin >> s >> p;
		words.insert(make_pair(s,p));
	}

	int m;
	cin >> m;
	for ( int i = 1; i <= m; ++i ) {
		string s;
		cin >> s;
		MyIt it = words.find(s);
        //k表示s出现的次数！！！！！
		int k = words.count(s), front = it->second;
		it++;
        //遍历寻找单词出现的最小页数
		for ( int v = 1; v < k; v++, it++ ) {
			if ( it->second < front ) {
				front = it->second;
			}
		}
		pages.insert(front);
	}
	
	cout << pages.size() << endl;
	return 0;
}