首页 > 试题广场 >

小红的正整数

[编程题]小红的正整数
  • 热度指数:295 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个正整数n,请你找到最大的正整数,满足该正整数所有数位之和等于n,且每个数位都不相等(每个数位不能是0)。
举个例子,如果n=7,那么答案是421。因为4+2+1=7,且每个数位都不相等。

输入描述:
一个正整数n
1\leq n \leq 100


输出描述:
如果不存在合法解,请输出-1。
否则输出最大的满足条件的正整数。
示例1

输入

7

输出

421
import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        if (n > 45) {
            System.out.println(-1);
            return;
        } else if (n < 3) {
            System.out.println(n);
            return;
        } else {
            int res = 0;
            ArrayList<Integer> nums = new ArrayList<>();
            int min = 1;
            int rest = 0;
            while (n != 0) {
                nums.add(min);
                n -= min;
                min++;
                if ((n - min) < (min + 1)) {
                   if (n<10 && n>0){
                       nums.add(n);
                   } else {
                       rest = n - 9;
                       nums.add(9);
                   } 
                    break;
                }
            }
            int times = 1;
            for (int i = nums.size() - 2; i >= 0; i--) {
                int cur = nums.get(i);
                if (rest <= 9 - times - cur) {
                    nums.set(i, cur + rest);
                    break;
                } else {
                    nums.set(i, 9 - times);
                    rest = rest - (9 - times - cur);
                    times++;
                }
            }
            for (int i = 0; i < nums.size(); i++) {
                res += nums.get(i) * Math.pow(10, i);
            }
            System.out.println(res);
        }
    }
}
维护状态,每次找到最小还原次数,然后向后向前遍历直到遇到0(Max_Value)

发表于 2023-03-16 16:22:46 回复(0)