首页 > 试题广场 >

最小数位和

[编程题]最小数位和

热度指数：3253 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

定义 $\mathit S(n)$ ，表示 $\mathit n$ 在十进制下的各位数字和。

现在给定一个 $\mathit x$ ,请你求出最小正整数 $\mathit n$ ，满足 $x \leq S(n)$ .

输入描述:

第一行数据组数，对于每组数据，一行一个数字。

输出描述:

对于每组数据，一行一个整数表示最小的。

示例1

输入

2
7
9

输出

7
9

示例2

输入

2 
13
18

输出

49  
99

算法知识视频讲解

Kuro丶Neko

import java.util.Scanner;
 
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        for(int i=0;i<length;i++){
            System.out.println(s(in.nextInt()));
        }
    }
     
    public static String s(int x){
        StringBuilder builder = new StringBuilder();
        while(x-9>0){
            builder.append("9");
            x-=9;
        }
        String result = String.valueOf(x)+builder.toString();
        return result;
    }
}

可以理解成一个分配数值的题目，每一数位是要分配的容器，容器大小是0-9，给定的x是要分配的值。要尽可能让这个数小，那么就得让末置位多分配一些数，最少的分配给前置位。所以每次分配先将个位数填满（最大为9），再将十位数填满，以此类推，直到分配完为止。

最后注意用String输出结果，否则会溢出

发表于 2020-04-26 03:55:52 回复(3)

JavaScript

Olivia_dtt

var n = parseInt(readline())
var arr = []
while(n > 0){
  var tmp = parseInt(readline())
  arr.push(tmp)
  n--
}
function foo(arr){
  var res = []
  for(var i = 0;i < arr.length;i++){
    var k = Math.floor(arr[i]/9) // 计算9有多少位，13/9 = 1 18/9=2 24/9=2
    var k1 = arr[i] % 9 // 最小数位和肯定是将余数放在最高位，其他位都是9
    var str = ''
    if(k1!==0){
        str+=`${k1}`
    }
    for(var j = 0;j < k;j++){
      str+='9'
    }
    res.push(str) // 49 99 699
  }
  return res
}
var res = foo(arr)
for(var i = 0; i< res.length;i++){
    console.log(res[i])
}

发表于 2020-04-05 22:35:41 回复(1)

胖虎喜欢静香

import java.util.Scanner;

/**
 * @author Mr.Zhao
 * @version 1.0
 * @Description:
 * @date 2020/1/5 10:48
 */
public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] arr = new int[i];
        for (int i1 = 0; i1 < i; i1++) {
            int j = scanner.nextInt();
            arr[i1] = j;
        }
        for (int i1 = 0; i1 < arr.length; i1++) {
            int k = arr[i1] / 9;
            int k1 = arr[i1] % 9;
            StringBuilder stringBuilder = new StringBuilder();
            if (k1 != 0) {
                stringBuilder.append(k1);
            }
            for (int i2 = 0; i2 < k; i2++) {
                stringBuilder.append(9);
            }
            System.out.println(stringBuilder);
        }
    }
}

发表于 2020-01-05 11:11:39 回复(1)

Chen95st

#第一行数据组数
T = int(input())
#每组一个数字，占一行
for i in range(T):
    x = int(input())
    n = str(x%9)
    for i in range(x//9):
        n += str(9)
    print(int(n))

编辑于 2020-07-23 14:46:24 回复(0)

Doing-

//位数之和等于x，且高位到低位非递减,这个数得最小
let len=parseInt(readline())
for(let i=0;i<len;i++){
    let num=parseInt(readline())
    //判断几位数
    let bit=Math.ceil(num/9)
    //一位数直接返回
    if(bit===1){
        console.log(num)
        continue
    }
    //多位数则除了首位，末位一定都是9
    let first=num-(bit-1)*9
    let last="9"
    while(bit>2){
        last+=9
        bit--
    }
    console.log(String(first)+last)
}

发表于 2022-04-16 13:24:31 回复(0)

牛客66217153号

T = int(input())
for i in range(T):
    x = int(input())
    if x < 10:
        n = x
    else:
        if x % 9 == 0:
            b = x // 9
            n = str(9)*b
        else:
            b = x // 9
            n = str(x % 9) + str(9)*b
    print(n)

发表于 2020-08-05 15:27:05 回复(0)

C/C++

击穿

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

char n_c(int n)
{
    return n + 48;
}

string X(int n)
{
    int count_n = n / 9;
    int remain = n % 9;
    string result_end = "";
    for (int i = 0; i < count_n; i++)
    {
        result_end += '9';
    }
    string result_n;
    if(remain!=0)
        result_n = n_c(remain)+result_end;
    else
        result_n = result_end;
    return result_n;
}

int main()
{
    int len_arr;
    cin >> len_arr;
    if (len_arr > 10 || len_arr < 1)
    {
        return 0;    //1<=T<=10
    }
    int* arr = new int[len_arr];
    for (int i = 0; i < len_arr; i++)
    {
        cin >> arr[i];
    }

    string* arr_res = new string[len_arr];

    for (int i = 0; i < len_arr; i++)
    {
        arr_res[i] = X(arr[i]);
    }

    for (int i = 0; i < len_arr; i++)
    {
        cout << arr_res[i] << endl;
    }

    return 0;
}

发表于 2020-02-11 13:39:36 回复(0)

FanFan520

表示看不懂题

发表于 2020-08-04 15:32:59 回复(5)

江边鸟

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m;
    cin>>T;
    long long x;
    while(T--){
        cin>>x;
        n=x/9;
        m=x%9;
        if(m!=0)
        cout<<m;
        for(int i=0;i<n;i++)
            cout<<"9";
        cout<<endl;
    }
     
    return 0;
}

10进制最大数是9，所以求9的除数就有几个9，余数就是最大位的数

发表于 2019-11-28 16:51:13 回复(1)

Yao!

C++，题意就是给你一个数字x，让你反推一个数字n，要求n的各位数之和等于x，而且n要最小
那么只有可能先从低位往高位填，比如：个位填满了（个位为9），才会去考虑填十位，以此类推

#include <iostream>
#include <vector>
using namespace std;

 void S(vector<int>& nums) {
     string str;

     for (int num : nums) {
         // 主要特别考虑num%9=0的情况
         if (num % 9 != 0)cout << num % 9;
         while (num >= 9) {
             cout << 9;
             num -= 9;
         }
         cout << endl;
     }
 }

 int main() {

     // 意思是反推一个数字，这个数字的各位数之和等于x，而且这个数字必须最小
     int n,num;
     vector<int> nums;
     cin >> n;
     while (n-- > 0) {
         cin >> num;
         nums.push_back(num);
     }
     S(nums);
     return 0;
 }

发表于 2022-09-03 12:33:07 回复(0)

RickySakura

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var arr = []
var T = null
rl.on('line', function (line) {
    arr.push(parseInt(line))
    if(arr[0] == arr.length-1){
        for (let i = 1; i < arr.length; i++) { 
           let n = parseInt(arr[i]/9)
           let f = arr[i] % 9
           let str = f==0?'':String(f)
           while(n>0){
               n--
               str += '9'
           }
            console.log(str)
         }
    }
    
    //console.log(arr)
});

解题思路：位数指的是个位，十位，百位这个位数，每个位数最大为 9，先填满低位的，剩余的在填到高位。输出采用字符串类型，不然会超出栈。

发表于 2022-08-13 01:20:12 回复(0)

牛客583575101号

思路：求和方法，遍历所有可能的n，放到一个数组中，求出数组里最大的n

function s(n){

    return [n*(n+1)]/2
}
function re(x){
    let resultArr = []
    for(let n=1;n<x;n++){
        let sum = s(n)
if(x<sum){
            resultArr.push(n)
}
}
let max = Math.max(...resultArr)
console.log('n=='+max)
}
re(5);

发表于 2020-11-19 14:43:44 回复(0)

牛客532766884号

var req = [10,13,7,29,29,25,10,13,31,8,16];

var res = [];

for(let i = 0 ; i<req[0] ; i++) {

let j = req[i+1];

let temp = '';

if(j-9<0) {

res.push(j);

}else{

while(j>=9) {

j-=9

temp+=9

}

if(j!=0) {

temp=j+temp;

}

let num = parseInt(temp);

res.push(num);

temp = '';

}

res.forEach((item,index,arr)=>{

console.log(item);

})

编辑于 2020-10-13 13:35:08 回复(0)

斐斐王P

#include<bits/stdc++.h>
using namespace std;
int main(){
    int i,n,m;
    cin>>i;
    long long x;
    while(i--){
        cin>>x;
        n=x/9;
        m=x%9;
        if(m!=0)
        cout<<m;
        for(int j=0;j<n;j++)
            cout<<"9";
        cout<<endl;
    }
    return 0;
}

发表于 2020-10-11 09:42:28 回复(0)

牛客609235308号

import java.util.Scanner;
  /**
  x<S(n),同等于x小于S(n)的最小值，十进制中，把后面位数的值（如个位数）设置越大，
  整个数的值越小，因为是十进制，位数最大值为9.
  **/
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);//输入字符
        int length = in.nextInt();//nextInt（）设置空格作为分隔
        for(int i=0;i<length;i++){//把分隔开的数字分别放入S(n)方法中
            System.out.println(s(in.nextInt()));
        }
    }
      
    public static String s(int x){
        StringBuilder builder = new StringBuilder();
        //当各位数字和大于9时，和-9,若小于9，这个数作为最高位
        while(x-9>0){
            builder.append("9");//将9追加到此字符序列
            x-=9;//各数字的总和x-9
        }
        String result = String.valueOf(x)+builder.toString();//最后小于9的数作为最高位，后面加上builder中追加的9
        return result;
    }
}

发表于 2020-09-11 20:01:23 回复(0)

YANZX

var num=parseInt(readline())
for(let i=0;i<num;i++){
    let _num=parseInt(readline())
    min(_num);
}
function min(num){
    let arr1=[];
    while(num>=10){
        num=num-9;
        arr1.push(9)
    }
    arr1.push(num);
 console.log(arr1.reverse().join("")) ;
}

编辑于 2020-09-03 11:03:56 回复(0)

Java

0OFFER救救我

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int group = sc.nextInt();
        for (int i = 0; i < group; i++) {
            System.out.println(func(sc.nextInt()));
        }
    }
    public static String func(int num) {
        StringBuffer sBuffer = new StringBuffer();
        while (num > 9) {
            sBuffer.append("9");
            num -= 9;
        }
        String res = String.valueOf(num) + sBuffer.toString();
        return res;
    }
}

发表于 2020-08-25 10:19:37 回复(0)

Morpwin

var nums = parseInt(readline());
for(var i = 0; i < nums; i++) {
    var x = parseInt(readline())
    if(x < 10) {
        print(x)
    }
    else {
        var str = ""
        while(x > 0) {
            if(x - 9 > 0) {
                str += "9"
                x = x - 9
            }
            else {
                str = x.toString() + str;
                x = 0
            }
        }
        print(str)
    }
}

发表于 2020-08-21 17:02:00 回复(0)

Python

又菜又想拿offer！

n=int(input())
for i in range(n):
    x=int(input())
    k=x//9
    m=x-9*k
    print int(str(m)+'9'*k)

编辑于 2020-08-08 11:01:33 回复(0)

阿杰不是本地人

def add_min(n):

    li=[]
    for i in range(n):
        a = 0
        x=int(raw_input())
        if x < 10:
            li.append(x)
        else:
            while x>=10:
                x=x-9
                a+=1
            li.append(x*(10**a)+(10**a-1))
    return li
n=int(raw_input())
li1=add_min(n)
for j in li1:
    print j

发表于 2020-08-08 09:55:41 回复(0)