蓝桥杯 ALGO-53 算法训练 最小乘积(基本型)

算法训练 最小乘积(基本型)  

时间限制：1.0s   内存限制：512.0MB

    

问题描述

　　给两组数，各n个。
　　请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。
　　例如两组数分别为:1 3　　-5和-2 4 1

　　那么对应乘积取和的最小值应为：
　　(-5) * 4 + 3 * (-2) + 1 * 1 = -25

输入格式

　　第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。
　　n<=8,T<=1000

输出格式

　　一个数表示答案。

样例输入

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

样例输出

-25
6

本人思路：

一开始在想，怎么样才能求出最小值呢。如果想两行数据相乘，然后相加的和最小，办法：一行数据由小到大，另一行数据由大到小，然后相乘，累加……bingo，第一行的最小值 乘以 第二行的最大值，……，第一行的最大值 乘以 第二行的最小值。

代码：

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for(int i=0;i<T;i++){
			int n = scanner.nextInt();
			int[][] a = new int[2][n];
			for(int j=0;j<2;j++){
				for(int k=0;k<n;k++){
					a[j][k]=scanner.nextInt();
				}
			}
			a=paixu(a);
			int sum=0;
			for(int j=0;j<n;j++){
				sum+=a[0][j]*a[1][j];
			}
			System.out.println(sum);
		}
	}

	//排序，将第一行和第二行进行排序
	public static int[][] paixu(int[][] arr){
		for(int i=0;i<2;i++){//一共有两行
			for(int j=0;j<arr[0].length;j++){
				for(int k=j+1;k<arr[0].length;k++){
					if(i==0){//第一行由小到大排序
						if(arr[i][j]>arr[i][k]){
							int temp=arr[i][j];
							arr[i][j]=arr[i][k];
							arr[i][k]=temp;
						}
					}else if(i==1){//第二行由大到小排序
						if(arr[i][j]<arr[i][k]){
							int temp=arr[i][j];
							arr[i][j]=arr[i][k];
							arr[i][k]=temp;
						}
					}
				}
			}
		}
		return arr;
	}
}