欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CSP认证2020-06-2-稀疏向量-Java语言100分

程序员文章站 2022-06-14 23:15:02
稀疏向量问题描述试题编号:202006-2试题名称:稀疏向量时间限制:2.0s内存限制:512.0MBJava 60分代码标准输入流处理不了第7-10测试点,所以只有60分。Java代码如下import java.util.Scanner;class Svector{ int index; int value;}public class Main { public static void main(String [] args){...

稀疏向量

问题描述
试题编号: 202006-2
试题名称: 稀疏向量
时间限制: 2.0s
内存限制: 512.0MB
CSP认证2020-06-2-稀疏向量-Java语言100分
CSP认证2020-06-2-稀疏向量-Java语言100分
CSP认证2020-06-2-稀疏向量-Java语言100分
最初用的数组标记,标记 a, b 的 index

int[] aflag = new int[n+1];
int[] bflag = new int[n+1];

Java整形数组是开不到109的,超出了内存分配空间,所以测试7-10是通不过的,只能拿60分。
计算最终结果使用long型的才行,如果使用 int ,测试7-10中满足不了106 * 106,即1012,超出了 int 的最大范围231-1,故依旧60分。
很多博主都说是Scanner的读取数据慢,导致60分,其实本题Scanner类也可以满分的。
测试了n遍,学了其他博主一些,终于算是满分通过了。
Java 100分代码
CSP认证2020-06-2-稀疏向量-Java语言100分
蓝色使用Scanner类读取数据几乎快接近限制时间和空间了,倒也是可以满分通过。
后来看了其他博主的优化方法,使用BufferedReader(红色),时间和空间都缩小了很多。
Java代码如下(Scanner类)

import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int[][] vector_a = new int[a][2];

        for(int i = 0;i < a;i++){
            vector_a[i][0] = sc.nextInt();
            vector_a[i][1] = sc.nextInt();
        }

        long sum = 0;
        int index_a = 0, b_index = 0, b_value = 0;
        for(int i = 0;i < b;i++){
            b_index = sc.nextInt();
            b_value = sc.nextInt();
            if(index_a < a && vector_a[index_a][0] == b_index){
                sum += vector_a[index_a][1]*b_value;
            }else{
                while(index_a < a && vector_a[index_a][0] < b_index){
                    index_a++;
                    if(index_a < a && vector_a[index_a][0] == b_index)
                        sum += vector_a[index_a][1]*b_value;
                }
            }
        }
        System.out.println(sum);
    }
}

Java代码如下(BufferedReader)

import java.io.*;

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] s = str.trim().split(" ");
        int n = Integer.valueOf(s[0]);
        int a = Integer.valueOf(s[1]);
        int b = Integer.valueOf(s[2]);
        int[][] vector_a = new int[a][2];

        for(int i = 0;i < a;i++){
            str = br.readLine();
            String[] s_a = str.trim().split(" ");
            vector_a[i][0] = Integer.valueOf(s_a[0]);
            vector_a[i][1] = Integer.valueOf(s_a[1]);
        }

        long sum = 0;
        int index_a = 0, b_index = 0, b_value = 0;
        for(int i = 0;i < b;i++){
            str = br.readLine();
            String[] s_b = str.trim().split(" ");
            b_index = Integer.valueOf(s_b[0]);
            b_value = Integer.valueOf(s_b[1]);
            if(index_a < a && vector_a[index_a][0] == b_index){
                sum += vector_a[index_a][1]*b_value;
            }else{
                while(index_a < a && vector_a[index_a][0] < b_index){
                    index_a++;
                    if(index_a < a && vector_a[index_a][0] == b_index)
                        sum += vector_a[index_a][1]*b_value;
                }
            }
        }
        System.out.println(sum);
    }
}

本文地址:https://blog.csdn.net/qq_45772965/article/details/109831112