C. Really Big Numbers

原题地址

http://codeforces.com/contest/817/problem/C

解题思想

/* 个人认为本题非常好。思想：二分查找 这个题为什么可以二分查找. 愿意是求,s<= x <=n 这样x的个数 假设满足题意的x的各个数字和为sumd(x) 这样的x为：x-x的个数字的和 >=s 即x-sumd(x) >=s 现在我们要想用二分查找，就必须证明若x满足，则x+1也满足 即证明 x+1 - sumd(x+1) >=s 根据样例1， 12 1，满足条件的为10,11,12 我们发现 sumd(10)=10-1=9 sumd(11)=11-2=9 sumd(12)=12-3=9 则sumd(10)+1=10>=sumd(11) 即sumd(x)+1>=sumd(x+1) 俩边同时加上x sumd(x)+1+x >= sumd(x+1)+x 移项得：x+1 - sumd(x+1) >= x - sumd(x) 又因为x-sumd(x) >= s 所以x+1 - sumd(x+1) >=s 即如果x满足条件，则x+1也满足条件 因此我们就可以用二分找出满足条件的最小x， 则结果就是n-x+1 */

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, s;

bool isTrue(ll num)
{
    int sum = 0;
    ll tem = num;
    while(num)
    {
        sum += num%10;
        num /=10;
    }
    return tem-sum >= s ? true : false;
}
int main()
{
    scanf("%lld%lld", &n,&s);
    ll left = s;
    ll right = n, mid;
    //二分查找最小的
    while(left <= right)
    {
        mid = (left+right) >> 1;
        if(isTrue(mid))
        {
            right = mid-1;
        }else
        {
            left = mid+1;
        }
    }
    //若n < s，则返回0
    ll ant = n-left+1;
    ant = ant < 0 ? 0 : ant;
    printf("%lld", ant);
    return 0;
}