AcWing 3288. 稀疏向量
原题链接
简单
作者:
不幸到吃土
,
2025-01-19 00:58:35
,
所有人可见
,
阅读 1
//双指针:i遍历向量u,j遍历向量v,若idx相同则相乘
#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
vector<PII> u,v;
int main(){
int n,a,b;
cin >> n >> a >> b;
while(a--){
int idx , val;
cin >> idx >> val;
u.push_back({idx,val});
}
while(b--){
int idx , val;
cin >> idx >> val;
v.push_back({idx,val});
}
LL res = 0;
int i=0 , j=0;
while(i<u.size() && j<v.size()){
if(u[i].x == v[j].x){
res+=(LL)u[i].y * v[j].y;
i++,j++;
}else if(u[i].x < v[j].x){
i++;
}else{
j++;
}
}
cout << res << endl;
return 0;
}
我用for循环错误情况的思考:
考虑这么一种情况:
u = 1 2 7 9 11
v = 8 11 12
i指向9,j指向11
而此时统一的i和j,使得两组都有的”11”被跳过了