稀疏向量（java)

向量（java)"/>

稀疏向量（java)

package ncu.edu.ccf;import java.util.Scanner;
//运行错误，60
public class XiShuXiangLiang_1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();int p = sc.nextInt();int q = sc.nextInt();int sum = 0;int[] u = new int[n];int[] v = new int[n];for(int i = 0; i<n; i++) {u[i]=0;v[i]=0;}for(int i = 0; i<p; i++) {int a = sc.nextInt();int b = sc.nextInt();u[a-1] = b;}for(int i = 0; i<q; i++) {int a = sc.nextInt();int b = sc.nextInt();v[a-1] = b;}for(int i = 0; i<n; i++) {sum = sum + (u[i]*v[i]);}System.out.println(sum);}}

package ncu.edu.ccf;import java.util.Scanner;
//第一次编译超时，90分；第二次满分
public class XiShuXiangLiang_3 {public static void main(String[] args) {// TODO Auto-generated method stub//1. 接收数据 n, a, bint n, a, b;Scanner scan = new Scanner(System.in);n = scan.nextInt();a = scan.nextInt();b = scan.nextInt();//2.1 接收向量 u 的稀疏表示数据int[] u_index = new int[a];int[] u_value = new int[a];for(int i=0; i<a; i++){u_index[i] = scan.nextInt();u_value[i] = scan.nextInt();}//3. 初始化最后结果long result = 0L;int v_index, v_value;int index_u = 0;for(int i=0; i<b; i++){v_index = scan.nextInt();	v_value = scan.nextInt();while(index_u < a && i<a && index_u < b){		if(u_index[index_u] == v_index){result += v_value * u_value[index_u];index_u++;break;}else if(u_index[index_u] < v_index){index_u++;}else{break;}}}//4. 输出结果System.out.println(result);}}