Java教程

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

本文主要是介绍试题 算法训练 预备爷的悲剧,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

题目

资源限制

时间限制: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;
}

这篇关于试题 算法训练 预备爷的悲剧的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!