文章目录
0 效果1 题目2 思路2.1 优化：
3 代码
0 效果
使用unordered_map（未排序key的散列map，速度比map快很多）【实际运行的速度比map满😂，这个就不知道编译怎么执行的了，可能是使用namespace导致的】 使用map 难点：性能优化，尽量减少时间和空间复杂度。
1 题目
2 思路
存储两个两个稀疏向量，如果两个稀疏向量相同的index上都有value（不为0），那么就用两个值相乘，计算所有这样乘积的和。
2.1 优化：
1 使用vector来优化存储第一个稀疏向量，以免开过大的全局数组；2 使用unordered_map来作为hash表映射index位置是否有值，使遍历的时间复杂度降至O(1)；3 使用unordered_map来存储第二个稀疏向量，避免遍历的第二个稀疏向量来寻找对应index的value的时间消耗。
3 代码
#include<cstdio>
#include<vector>
#include <tr1/unordered_map>
namespace std
{
using std
::tr1
::unordered_map
;
}
#include<map>
typedef struct Data
{
int first
, second
;
Data(int _first
, int _second
):first(_first
), second(_second
){}
}data
;
std
::unordered_map
<int, bool> savePosition
;
std
::vector
<data
> A
;
std
::unordered_map
<int, int> B
;
int main(){
int n
, a
, b
;
scanf("%d%d%d", &n
, &a
, &b
);
while(a
--){
int index
, value
;
scanf("%d%d", &index
, &value
);
A
.push_back(data(index
, value
));
}
while(b
--){
int index
, value
;
scanf("%d%d", &index
, &value
);
B
[index
] = value
;
savePosition
[index
] = true;
}
long long res
= 0;
for(std
::vector
<data
>::iterator i
= A
.begin(); i
!= A
.end();i
++){
if(savePosition
[i
->first
] == true){
res
+= i
->second
*B
[i
->first
];
}
}
printf("%lld", res
);
return 0;
}
