202006-2 稀疏向量

输入输出样例

样例1

输入

10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

输出

-20

题解一

60分。超时。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, key, value; i < a; ++i) {
            key = scanner.nextInt();
            value = scanner.nextInt();
            map.put(key, value);
        }
        long ans = 0;
        for (int i = 0, key, value; i < b; ++i) {
            key = scanner.nextInt();
            value = scanner.nextInt();
            if (map.containsKey(key)) {
                ans += map.get(key) * value;
            }
        }
        System.out.println(ans);
    }
}

题解二

60分。超时。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        Pair[] arrA = new Pair[a];
        Pair[] arrB = new Pair[b];
        for (int i = 0; i < a; ++i) {
            arrA[i] = new Pair(scanner.nextInt(), scanner.nextInt());
        }
        for (int i = 0; i < b; ++i) {
            arrB[i] = new Pair(scanner.nextInt(), scanner.nextInt());
        }
        long ans = 0;
        int ptrA = 0;
        int ptrB = 0;
        while ((ptrA < arrA.length) && (ptrB < arrB.length)) {
            if (arrA[ptrA].key == arrB[ptrB].key) {
                ans += arrA[ptrA].value * arrB[ptrB].value;
                ++ptrA;
                ++ptrB;
            } else if (arrA[ptrA].key > arrB[ptrB].key) {
                ++ptrB;
            } else {
                ++ptrA;
            }
        }
        System.out.println(ans);
    }
}
class Pair {
    int key;
    int value;
    public Pair(int key, int value) {
        super();
        this.key = key;
        this.value = value;
    }
}

题解三

居然是因为读入效率的问题。。。换成BufferedReader后满分通过。
参考链接：https://blog.csdn.net/tylz970408/article/details/108205028?utm_medium=distribute.pc_relevant.none-task-blog-blogcommendfrommachinelearnpai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-blogcommendfrommachinelearnpai2-2.channel_param

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = reader.readLine().trim().split(" ");
        int n = Integer.parseInt(strs[0]);
        int a = Integer.parseInt(strs[1]);
        int b = Integer.parseInt(strs[2]);
        Pair[] arrA = new Pair[a];
        Pair[] arrB = new Pair[b];
        String[] s;
        for (int i = 0; i < a; ++i) {
            s = reader.readLine().trim().split(" ");
            arrA[i] = new Pair(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
        }
        for (int i = 0; i < b; ++i) {
            s = reader.readLine().trim().split(" ");
            arrB[i] = new Pair(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
        }
        long ans = 0;
        int ptrA = 0;
        int ptrB = 0;
        while ((ptrA < arrA.length) && (ptrB < arrB.length)) {
            if (arrA[ptrA].key == arrB[ptrB].key) {
                ans += arrA[ptrA].value * arrB[ptrB].value;
                ++ptrA;
                ++ptrB;
            } else if (arrA[ptrA].key > arrB[ptrB].key) {
                ++ptrB;
            } else {
                ++ptrA;
            }
        }
        System.out.println(ans);
    }
}
class Pair {
    int key;
    int value;
    public Pair(int key, int value) {
        super();
        this.key = key;
        this.value = value;
    }
}