摘要
Title: 3288. 稀疏向量
Tag: 哈希表、双指针
Memory Limit: 64 MB
Time Limit: 1000 ms

3288. 稀疏向量

题意

见原题
思路
- 哈希表存下有数值的即可，枚举A，如果B中有对应的就乘即可
- 由于是有序的，也可以通过双指针，从最合适的j

代码

注意,记录两个哈希表会超时

from collections import Counter
n, a, b = map(int, input().split())
ans = 0

map_u = Counter()
for i in range(a):
    i, v = map(int, input().split())
    map_u[i] = v

for i in range(b):
    i, v = map(int, input().split())
    if map_u[i]:
        ans += v * map_u[i]

print(ans)

双指针

'''
Author: NEFU AB-IN
Date: 2022-03-19 13:20:09
FilePath: \ACM\Acwing\3288.1.py
LastEditTime: 2022-03-19 13:49:06
'''


class Node():
    def __init__(self, id, v):
        self.id = id
        self.v = v


n, a, b = map(int, input().split())

A, B = [], []

for i in range(a):
    id, v = map(int, input().split())
    A.append(Node(id, v))
for i in range(b):
    id, v = map(int, input().split())
    B.append(Node(id, v))

j, ans = 0, 0
for i in range(a):
    while j < b and B[j].id < A[i].id:
        j += 1
    if j < b and B[j].id == A[i].id:
        ans += B[j].v * A[i].v
print(ans)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long LL;

unordered_map<int, LL> A, B;

int n, a, b;
int id, value;


int main()
{
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 0; i < a; i ++ ){
        scanf("%d%d", &id, &value);
        A[id] = value;
    }
    for (int i = 0; i < b; i ++ ){
        scanf("%d%d", &id, &value);
        B[id] = value;
    }
    LL ans = 0;
    for(auto [id, value] : A){
        if(B[id]){
            ans += A[id] * B[id];
            A[id] = 0;
            B[id] = 0;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

3288. 稀疏向量

题意

思路

代码