专栏首页AI那点小事算法训练 最小乘积(基本型)

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

问题描述   给两组数,各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

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int cnt = in.nextInt();
        for ( int i = 0 ; i < cnt ; i++){
            int len1 = in.nextInt();
            int[] arr1 = new int[len1];
            int[] arr2 = new int[len1];
            for ( int j = 0 ; j < len1 ; j++){
                arr1[j] = in.nextInt();
            }
            for ( int j = 0 ; j < len1 ; j++){
                arr2[j] = in.nextInt();
            }
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            int min = 0;
            for ( int j = 0 ; j < len1 ; j++){
                min += arr1[j] * arr2[len1-j-1];
            }
            System.out.println(min);
        }
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 创造新世界

    众所周知计算机代码底层计算都是0和1的计算,牛牛知道这点之后就想使用0和1创造一个新世界!牛牛现在手里有n个0和m个1,给出牛牛可以创造的x种物品,每种物品都由...

    AI那点小事
  • 寻找大富翁

    题目描述 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入描述: 输入包含多组测试用例. 每个用例首先包含2个...

    AI那点小事
  • 09-排序2 Insert or Merge (25分)

    Insertion sort iterates, consuming one input element each repetition, and growin...

    AI那点小事
  • Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) C. Connect(bfs)

    题目链接:http://codeforces.com/contest/1130/problem/C

    Ch_Zaqdt
  • 二分问题-LeetCode 69、167、92(二分,牛顿法,双指针)

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    算法工程师之路
  • 种树 差分约束|贪心

    每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。

    用户2965768
  • 设计模式-单例模式

    单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一。

    Anymarvel
  • 敏捷开发与 DevOps 实战【含源码】

    随着互联网、移动互联网的浪潮,软件工程从瀑布到敏捷发生了巨大的变化,服务器架构也从 IOE 演变到微型机,又发展为云计算,运维成本越来越低,持续部署逐渐流行起来...

    腾讯云大学
  • Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths(dfs染色)

    版权声明:欢迎转载,若转载,请标明出处,如有错误,请指点,也欢迎大佬们给出优化方法 https://blog.csdn.net/Charles_Zaqd...

    Ch_Zaqdt
  • Java常用排序算法/程序员必须掌握的8大排序算法

    1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)

    哲洛不闹

扫码关注云+社区

领取腾讯云代金券