CCF-CSP 202009-2 稀疏向量
问题描述代码总结
问题描述
代码
#include <iostream>
using namespace std
;
struct svector
{
int index
;
int value
;
};
int main(){
int n
,a
,b
;
cin
>>n
>>a
>>b
;
svector u
[a
];
svector v
[b
];
int p
,q
;
for(int i
=0;i
<a
;i
++){
cin
>>p
>>q
;
u
[i
].index
=p
;
u
[i
].value
=q
;
}
for(int i
=0;i
<b
;i
++){
cin
>>p
>>q
;
v
[i
].index
=p
;
v
[i
].value
=q
;
}
long long sum
=0;
for(int i
=0,j
=0;i
<a
&& j
<b
;){
if(u
[i
].index
== v
[j
].index
){
sum
= sum
+ u
[i
].value
* v
[j
].value
;
i
++;
j
++;
}
else if(u
[i
].index
> v
[j
].index
){
j
++;
}
else{
i
++;
}
}
cout
<<sum
<<endl
;
return 0;
}
总结
本题的问题主要在于测试点中7，8，9，10的n值过大，会超时，所以不能暴力使用遍历，否则这题就过于简单了。因此绝不能在最后的循环中使用n作为循环结束的上限。 还有一个问题在于sum的数据类型要声明为long long，否则长度不够存不下。
