数据结构算法（Given Length and Sum of Digits）

https://codeforces.com/problemset/problem/489/C

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.Input

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.Output

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).ExamplesinputCopy

2 15

outputCopy

69 96

inputCopy

3 0

outputCopy

-1 -1

---

最开始思路：把大的尽量每一位大着放，然后小的倒着枚举9.然后发现这么做有各种特判..最后wa44..

//int main(void)
//{
//  cin.tie(0);std::ios::sync_with_stdio(false);
//  LL m,s;cin>>m>>s;
//  if(m!=1&&s==0||m*9<s)
//  {
//  	cout<<"-1"<<" "<<"-1"<<endl;	
//  } 
//  else
//  {
//  	 //mininum
//  	 LL p1=s;LL cnt1=p1/9;p1-=cnt1*9;//p1为剩下的 
//  	 if(m>1)
//  	 {
//	 	if(cnt1==m)
//	 	{
//	 		for(LL i=1;i<=m;i++) a[i]=9;
//	 	}
//	 	else
//	 	{
//	 		for(LL i=m;i>=m-cnt1+2;i--) a[i]=9;
//			a[1]=1;a[m-cnt1+1]=8;			
//	 	}
//	 }
////	 else if(m!=1)
////	 {
////	 	a[m]=s-1;a[1]=1;
////	 }
//	 else 
//	 {
//	 	a[1]=s;
//	 }
//	 //maximun
//	 LL p2=s;LL cnt2=0;
//	 if(p2>=9)
//	 {
//	 	while(p2>=9)
//	 	{
//	 		b[++cnt2]=9;p2-=9;
//	 	}
//	 	b[++cnt2]=p2;
//	 }
//	 else b[++cnt2]=p2;
//	 //输出最小 
//	 for(LL i=1;i<=m;i++) cout<<a[i];
//	 cout<<" ";
//	 //输出最大
//	 for(LL i=1;i<=m;i++) 
//	 {
//	 	cout<<b[i];	
//	 } 
//  }
//return 0;
//}

---

思路：利用对称性去考虑。最大的字串很容易构造出来。最小的是最大的reverse（）一下。然后首位是1的就往后找第一个不是0的拿一个过来

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
LL a[maxn],b[maxn];
int main(void)
{
	LL m,s;cin>>m>>s;
	if(m==1&&s==0) cout<<0<<" "<<0<<endl;
	else if(s==0||m*9<s) cout<<-1<<" "<<-1<<endl;
	else
	{
		//先构造最大数
		string str1;
		for(LL i=0;i<m;i++)
		{
			LL x=min(s,(LL)9);
			s-=x;
			//str1[i]=char(x+'0'); 输出失败了..
			str1+=char(x+'0');							
		} 
		string k=str1;
		reverse(str1.begin(),str1.end());//无返回值 
		if(str1[0]=='0')
		{
		  for(LL i=0;i<str1.size();i++)
		  {
		  	 if(str1[i]!='0')
		  	 {
		  	 	str1[i]--;
				str1[0]='1';
				break;    	
			 }
		  }
		}
		cout<<str1<<" "<<k<<endl; 
	}
}

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/107775911