Codeforces - 489C - Given Length and Sum of Digits...

Question

题目大意

给你两个数 m 、 s ，要你用 m 个 0~9 之间的数”组成“他们之和为 s ，这里的组成就是这些数的和为 s ，要你求这样的数的最小值和最大值。

解析

细节有一点多的贪心题，错了好几次。。。注意细节就好:

• 贪心的思想: 最小的大概是 100009999 类似这种，最大的是类似 9999910000 这种。最大值容易考虑，最小值的要注意很多情况；
• 注意输出 -1 -1 的情况即: (s == 0 && m > 1) || s > m * 9 ；
• 注意特殊情况例如 m = 3，s = 9 ，不能输出 099 ，而是 108 ，不能有前导 0 ，所以也要特殊考虑；

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int m = cin.nextInt();
        int s = cin.nextInt();
        int nineNum = s/9; // the num of 9 should be output
        int remainder = s%9;
        int left = m - nineNum;
        if((s == 0 && m > 1) || s > m * 9)
            System.out.println("-1 -1");
        else { 
            StringBuilder minn = new StringBuilder();
            StringBuilder maxx = new StringBuilder();
            if(remainder == 0 && m > 1 && left != 0) { // all number is 9 and left != 0 --> but can't have leading 0
                if(left > 0) {
                    if (left == 1) {
                        minn.append(remainder);
                    } else {
                        minn.append(1);
                        for (int i = 0; i < left - 1; i++) //not left-2
                            minn.append(0);
                        minn.append(8); // 分担出一个
                    }
                }
                for (int i = 0; i < nineNum-1; i++) { // not nineNum
                    minn.append(9);
                }
            }else {
                if(left > 0) {
                    if (left == 1) {
                        minn.append(remainder);
                    } else {
                        minn.append(1);
                        for (int i = 0; i < left - 2; i++)
                            minn.append(0);
                        minn.append(remainder - 1);
                    }
                }
                for (int i = 0; i < nineNum; i++) {
                    minn.append(9); 
                }
            }
            System.out.print(minn + " " );

            // deal with max value --> easy
            for (int i = 0; i < nineNum; i++)
                maxx.append(9);
            if(left > 0) {
                maxx.append(remainder);
                for (int i = 0; i < left - 1; i++)
                    maxx.append(0);
            }
            System.out.println(maxx);
        }
    }
}