宁夏交通建设质监局官方网站/广告关键词有哪些

一、题目

二、解析

主要用到map的构造和find方法。其中，map的构造如下：

#include <iostream>
#include <map>using namespace std;int n, a, b;map<int, int> u;
map<int, int> v;int main()
{cin >> n >> a >> b;for (int i = 0; i < a; i++) {int ind, val;cin >> ind >> val;u[ind] = val;}for (int i = 0; i < b; i++) {int ind, val;cin >> ind >> val;v[ind] = val;}cout << "Vector u:" << endl;for (map<int, int>::iterator it = u.begin(); it != u.end(); it++)cout << (*it).first << " " << (*it).second << endl;cout << "Vector v:" << endl;for (map<int, int>::iterator it = v.begin(); it != v.end(); it++)cout << (*it).first << " " << (*it).second << endl;return 0;
}

输入：

10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

输出：

Vector u:
4 5
7 -3
10 1
Vector v:
1 10
4 20
5 30
7 40

三、代码

#include <iostream>
#include <map>using namespace std;int n, a, b;map<int, int> u;
map<int, int> v;long long product = 0;int main()
{cin >> n >> a >> b;for (int i = 0; i < a; i++) {int ind, val;cin >> ind >> val;u[ind] = val;}for (int i = 0; i < b; i++) {int ind, val;cin >> ind >> val;v[ind] = val;}//	cout<<"Vector u:"<<endl;//	for(map<int, int>::iterator it=u.begin(); it!=u.end(); it++)//		cout<<(*it).first<<" "<<(*it).second<<endl;////	cout<<"Vector v:"<<endl;//	for(map<int, int>::iterator it=v.begin(); it!=v.end(); it++)//		cout<<(*it).first<<" "<<(*it).second<<endl;for (map<int, int>::iterator itU = u.begin(); itU != u.end(); itU++) {int ind = (*itU).first;map<int, int>::iterator itV = v.find(ind);if (itV != v.end())product += (*itU).second * (*itV).second;}cout << product << endl;return 0;
}

输入：

10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

输出：

-20

四、感想

1. 第一次使用vector，但只获得30分，后面的超时了。因为vector的查找的时间复杂度为O(n)，所以程序的时间复杂度为O(a*b)。

2. 第二次使用map，但只获得60分，后面的错误了；第三次将累加用的变量product由int类型换为long long类型，就通过了。因为map的查找的时间复杂度为O(log n)，所以程序的时间复杂度为O(a*log b)；且|u_i|、|v_i|<=10⁶，故product的类型应该为long long。