算法訓(xùn)練最小乘積(基本型)

2019-11-08 18:29:51

字體：大中小

供稿：網(wǎng)友

算法訓(xùn)練最小乘積(基本型) 時間限制：1.0s 內(nèi)存限制：512.0MB 問題描述　　給兩組數(shù)，各n個。　　請調(diào)整每組數(shù)的排列順序，使得兩組數(shù)據(jù)相同下標(biāo)元素對應(yīng)相乘，然后相加的和最小。要求程序輸出這個最小值。　　例如兩組數(shù)分別為:1 3　　-5和-2 4 1　　那么對應(yīng)乘積取和的最小值應(yīng)為：　　(-5) * 4 + 3 * (-2) + 1 * 1 = -25輸入格式　　第一個行一個數(shù)T表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)，先讀入一個n，接下來兩行每行n個數(shù)，每個數(shù)的絕對值小于等于1000。　　n<=8,T<=1000輸出格式　　一個數(shù)表示答案。樣例輸入

231 3 -5-2 4 151 2 3 4 51 0 1 0 1
樣例輸出
-256
思路：將兩個數(shù)組一個升序，一個降序，然后對應(yīng)下標(biāo)的值相稱的和即為結(jié)果
import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;public class Main {	public static void main(String[] args) {		Scanner scan = new Scanner(System.in);		int T = scan.nextInt();		while(T--!=0){			int n = scan.nextInt();			int[] a = new int[n];			int[] b = new int[n];			for(int i=0;i<n;i++)				a[i] = scan.nextInt();			for(int i=0;i<n;i++)				b[i] = scan.nextInt();			Arrays.sort(a);			Arrays.sort(b);			int ans = 0;			for(int i=0;i<n;i++){				ans += a[i]*b[n-i-1];			}			System.out.PRintln(ans);		}	}}