我没有用二分法，直接构造最小数，既然题目保证答案一定存在那么与上界无关。
如给定S=16，它能构成的最小数为79，尽量用9补位，最高位为S%9.如果构造的数大于下界A，那么直接输出，因为这是S能构成的最小数；小于下界就要分两种情况了，第一种情况就是A的各位的和P小于S，那么从最低位一直向高位不，最高补9，补不到9，就补能补的最大数；第二种情况就是P大于S，那么就从最高位枚举，看能否补成和A同样的数，如不能立即返回上一位，加1，如果小于9，那么高位确定，剩下的就利用“尽量用9补位，最高位为S%9”的方法构造。
这题还有个坑人的地方，题目并没有说是多数据输入，但是如果用单组数据数据，会WA
AC代码：
#include<cstdio>
#include<cstring>
const int maxn=23;
char a[maxn],b[maxn];
int tmp[maxn],ans[maxn],c;
int main(){
while(scanf("%s%s%d",a,b,&c)==3){
int lenth=strlen(a);
long long x=0;
for(int i=0;i<lenth;++i){
tmp[i+1]=a[i]-'0';
x=x*10+a[i]-'0';
}
int num=c;
tmp[0]=ans[0]=0;
long long y=num%9;
for(int i=0;i<num/9;++i)
y=y*10+9;
if(y>=x) printf("%lld",y);
else if(y<x){
int p=0;
lenth++;
for(int i=1;i<lenth;++i)
p+=tmp[i];
if(p<=num){
for(int i=0;i<lenth;++i)
ans[i]=tmp[i];
num-=p;
for(int i=lenth-1;i>=0&&num>0;--i){
if(ans[i]+num>=9){
num-=9-ans[i];
ans[i]=9;
}
else {
ans[i]+=num;
num=0;
}
}
if(ans[0]) printf("%d",ans[0]);
for(int i=1;i<lenth;++i)
printf("%d",ans[i]);
}
else {
int h=num,ind;
for(int i=0;i<lenth;++i){
ans[i]=0;
if(tmp[i]>ans[i]){
num-=tmp[i]-ans[i];
ans[i]=tmp[i];
}
if(num<=0){
int k;
for(k=i-1;k>=0;--k){
ans[k]++;
if(ans[k]<10) break;
}
ind=k+1;
break;
}
}
for(int i=0;i<ind;++i)
h-=ans[i];
for(int i=ind;i<lenth;++i)
ans[i]=0;
for(int i=lenth-1;i>lenth-1-h/9;--i)
ans[i]=9;
if(h%9) ans[lenth-1-h/9]=h%9;
if(ans[0]) printf("%d",ans[0]);
for(int i=1;i<lenth;++i)
printf("%d",ans[i]);
}
}
printf("\n");
}
return 0;
}
如有不当之处欢迎指出！