题目的要求其实就是一个计算向量点乘的问题，只是题中给出的“稀疏向量”中有很多0，我们要做的就是根据给出的非零值，直接计算出两个向量的内积。
从题目给出的定义来看，index和value是一一对应的键值对，可以用STL的map来实现，也可以自定义结构体用数组来存储，这里我用结构体来实现：
typedef struct nzero {
int index;
int value;
}nzero;
下面我们根据样例来分析解题步骤：
由于两个向量除了给出维度的值，其余维度都为0，所以我们在计算内积时，只有两个向量在同一维度上都不为0才需要进行计算。由上图样例1所示，u和v两个数组中，只有存在相同index值的value才能参与计算。
于是我们的解题关键就在于找出u和v两个数组中具有相同index的项。
这是一个简单问题，用嵌套for循环就可以实现，对于u中每一项的index，遍历v，寻找相同的index即可。但是题中给出的a,b（u,v数组的规模）最大可达到 5 × 1 0 5 5×10^5 5×105，如果对u中每一项都遍历v来判断，时间复杂度最大就会超过 O ( 1 0 10 ) O(10^{10}) O(1010)，必然会导致超时。
所以我们对内层循环应该进行优化，看看能否减少循环次数。
根据样例1，我们会发现u和v在输入时是按照index升序排列的，其实就是一个向量的值是按维度从小到大来写的。而我们在推导遍历样例时会发现，其实对于u中的每一个index，并不需要对v从头到尾遍历，接着上一次的继续往下寻找就可以完成要求。于是我们可以对v数组引入一个指针（只是类似指针一样指向下标，并不需要真的指针），在遍历u的过程中同时对v遍历，最终两个数组都只需要遍历一遍，这样一来时间复杂度最大就只有 O ( 1 0 6 ) O(10^6) O(106)，就不会超时了。
但是题中只给出了一个样例，我们并不能保证其他测试样例在输入值就会按index值升序排列，因此我们在输入完之后需要先对u和v进行排序：
bool cmp(nzero a, nzero b) {
return a.index < b.index;
}
sort(u, u+a, cmp);
sort(v, v+b, cmp);
注：由于每个value绝对值最大可达到 1 0 6 10^6 106，因此最终的结果应定义成long long类型，不然会导致结果错误。
完整满分代码贴在最后：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct nzero {
int index;
int value;
}nzero;
bool cmp(nzero a, nzero b) {
return a.index < b.index;
}
nzero u[1000010], v[1000010];
int main() {
int n, a, b;
cin >> n >> a >> b;
for(int i=0; i<a; i++) {
cin >> u[i].index >> u[i].value;
}
for(int i=0; i<b; i++) {
cin >> v[i].index >> v[i].value;
}
//将所有键值对按index升序排列：
sort(u, u+a, cmp);
sort(v, v+b, cmp);
long long sum = 0; //最终的内积结果（不开long long结果会错误）
int temp = 0; //v数组下标的指针。临时变量
for(int i=0; i<a; i++) {
while(v[temp].index < u[i].index && temp<b) temp++;
if(temp >= b) break;
if(v[temp].index == u[i].index) {
sum += v[temp].value * u[i].value;
temp++;
}
}
cout << sum;
return 0;
}
