拼多多2021-7-25 笔试 第四题

题目描述：给定0-9组成的任意数字字符串 其数字可重复 通过该字符串插入乘号(不限数量) 使得得到的乘法结果最大
思路：贪心构造两个最大最接近的乘数
ps：乘号插入后的结果一定小于原数，所以只插一个乘号即可，被迫至少插一个，插多的话会变小
证明：
abcde=abc x 100 + de
abc x de <=abc x 99
前者大于后者，乘号放哪都一样满足这个

import java.math.BigInteger;
import java.util.Scanner;
//拼多多 2021-7-25 笔试 第四题
//题目描述：给定0-9组成的任意数字字符串 其数字可重复 通过该字符串插入乘号(不限数量) 使得得到的乘法结果最大
public class Solution1 {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        //接收0-9每种数字的数量
        int[] input=new int[10];
        for (int i = 0; i < 10; i++) {
            input[i]=s.nextInt();
        }
        //根据数量，从0-9的去取数字构造字符串，这里取完了就排序好了
        StringBuilder input_s= new StringBuilder();
        for (int i = 0; i < 10; i++) {
            if(input[i]>0){
                for (int j = 1; j <=input[i] ; j++) {
                    input_s.append(""+i);
                }
            }
        }
        //System.out.println(input_s);
        System.out.println(fun(input_s.toString()));
        //System.out.println(new BigInteger(97632+"").multiply(new BigInteger("87541")));
    }
    //从输入的数堆中尝试构造两个最大最接近的数   每次取两个最大的数，想办法接到乘数1，和乘数2上，使它们最接近
    static public String fun(String input_s) {
        //开一个方向标记
        int mark = 1;
        int i = input_s.length() - 1;
        String mutiy1 = "", mutiy2 = "";
        //尝试取数构造
        while (i >=0) {
            //每次追加交换方向  比如上次是先给乘数1追加，这次就先给乘数2追加，这样，乘数1和2才始终最接近
            if(i>=1) {
                if (mark == 1) {
                    mutiy1 += input_s.charAt(i);
                    i--;
                    mutiy2 += input_s.charAt(i);
                    i--;
                    mark = 2;
                }
                else {
                    mutiy2 += input_s.charAt(i);
                    i--;
                    mutiy1 += input_s.charAt(i);
                    i--;
                    mark = 1;
                }
            }
            //如果最后单独剩余一个数，分别追加到乘数1或2上，返回大的乘法结果值
            if (i == 0) {
                BigInteger res1 = new BigInteger(mutiy1 + input_s.charAt(0)).multiply(new BigInteger(mutiy2));
                BigInteger res2 = new BigInteger(mutiy1).multiply(new BigInteger(mutiy2 + input_s.charAt(0)));
                if (res1.compareTo(res2) < 0) {
                    return res2.toString();
                } else {
                    return res1.toString();
                }
            }
        }
        BigInteger res = new BigInteger(mutiy1).multiply(new BigInteger(mutiy2));
        return res.toString();
    }
}