CF489C Given Length and Sum of Digits

向右看齐 2023-10-01 17:26 11阅读 0赞

题目： Given Length and Sum of Digits  ，哈哈，我们今天来看一道比较简单的贪心题，虽然比较简单，但是如果不仔细的话很容易出错的额，这是选自codeforce 489C上的一道题，好了，我们一起来看看题意吧：

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！  
题目链接： [Given Length and Sum of Digits][]

### 题目描述 ###

You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.

### 输入描述 ###

> The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.

### 输出描述 ###

> In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers “-1 -1” (without the quotes).

**示例1**

`输入`

> 2 15

`输出`

> 69 96

**示例2**

`输入`

> 3 0

`输出`

> \-1 -1

`思路`:

> 求最大值时，我们从高位到低位能填9一定要填9,填完看情况是否补0，这样才会最大,最小值就是将最大值逆序（若最大值末尾时0，将其设置为1，然后从低位+1往高位看，将第一个非0的数减1），具体的思路就看代码吧，有注释的！

`我们来看看成功AC的代码吧：`

#include<bits/stdc++.h>
    using namespace std;
    int m,s;
    string mmax,mmin;
    int f(){
        
        if(m*9<s) return 0;
        if(s==0&&m!=1) return 0;
        return 1;
    }
    int main(){
        
        cin.tie(0);
        ios::sync_with_stdio(false);
        cin>>m>>s;
        if(!f()) {
        cout<<"-1 -1\n"; return 0;}
        int t=s;
        while(t>0){
        
            if(t>=9) mmax+='9',t-=9;
            if(t<9&&t!=0) mmax+=(t+'0'),t-=9;
        }
        int len1=mmax.length();
        for(int i=1;i<=(m-len1);i++) mmax+='0';//要补0的情况 
        mmin=mmax;
        if(len1!=m&&len1!=0){
        //若len1不等于m且不等于0（因为len1等于0的情况就是s=0 ），那么 mmin就需要处理,然后再逆转，否则 mmin就是mmax的逆序
            mmin[m-1]='1';//将最后1位0改为1,
            for(int i=m-2;i>=0;i--)//相应的将前面的第一个非0的减掉一个
                if(mmin[i]!='0') {
        mmin[i]=((mmin[i]-'0')-1)+'0'; break;}
        }
    	reverse(mmin.begin(),mmin.end());//逆转则是答案
        cout<<mmin<<" "<<mmax;
        return 0;
    }

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!

[Given Length and Sum of Digits]: https://codeforces.com/problemset/problem/489/c