python 6行解法

看评论都是说用二分法。我怎么就没想到呢？貌似我用的是“十分法”哈哈。

提供一种极为简单易懂的思路：

就拿题目的564举例：

1. 我们要找到一个数x，经过一系列擦掉最后一位操作后，和为564。

2. 首先要确定x的位数，它一定是三位或两位（如果是四位，结果肯定是四位）。在此我们就假定它是三位数abc(就算最终结果是两位数，那么求出来a=0就可以了)。经过一系列擦操作之后：abc + ab + a = 564，

   即：(a * 100 + b * 10 + c) + (a * 10 + b) + (a) =564;

   即 ：111 * a + 11 * b + 1 * c = 564

   我们想要求a、b、c，很简单，a = 564 // 111 = 5（"//"表示取整操作）

   此时564 - 111 * 5 = 9。接下来要求b：b = 9//11 = 0

   此时 9 - 0 * 11 = 9。接下来要求c:c = 9//1 = 9

   最终结果5->0->9

3. 扩展到四位数x，它的形式一定是1111 * a + 111 * b + 11 * c + 1* d = x

   同理扩展到n位数。

根据上面的思路，代码就简单了：

string = input()
num, res = int(string), ""
for i in range(len(string), 0, -1):
    res += str(num // int(i * "1"))
    num = num % int(i * "1")
print(res if int(res) < int(string) else -1)

如果判断找不到x呢，如果求出来结果比输入的数大，肯定是不对的，此时输出-1

#include<stdio.h>
long long getSum(long long);
int main(){
    long long sum,l,r,mid;
    //freopen("input.txt","r",stdin);
    scanf("%lld",&sum);
    for(l=0,r=sum;l+1<r;){
        mid=l+(r-l)/2;
        if(getSum(mid)==sum){
            printf("%lld",mid);
            return 0;
        }else if(getSum(mid)<sum) l=mid;
        else r=mid;
    }
    if(getSum(l)==sum) printf("%lld",l);
    else if(getSum(r)==sum) printf("%lld",r);
    else printf("-1");
}
long long getSum(long long x){
    long long sum=0;
    while(x!=0) sum+=x,x/=(long long)10;
    return sum;    
}//数据这么大，一看就是二分啦~

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        if(str==null||str.length()==0){
            System.out.println("-1");
            return;
        }

        long res = Long.parseLong(str);
        List<Long> list = new LinkedList<>();

        for (int i = str.length(); i >0 ; i--) {
            long listItem = res/num(i);
            list.add(listItem);
            res = res - listItem*num(i);
        }

        res=0;
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i)>9){
                System.out.println("-1");
                return;
            }
            res=list.get(i)+res*10;
        }

        System.out.println(res);
    }

    public static long num(int len){
        long  sum = 0;
        for (int i = 0; i < len; i++) {
            sum=sum*10+1;
        }
        return sum;
    }


}

#include <bits/stdc++.h>
using namespace std;

long F(long x){
    long s = 0;
    while(x){
        s += x;
        x /= 10;
    }
    return s;
}

long BS(long s){
    long l=s-(s/10)*2, r=s, m, sm;
    while(l<=r){
        m = (l+r)>>1;
        sm = F(m);
        if(sm > s)
            r = m - 1;
        else if(sm < s)
            l = m + 1;
        else
            return m;
    }
    return -1;
}

int main(){
    long s, x;
    scanf("%ld", &s);
    x = BS(s);
    printf("%ld\n", x);
    return 0;
}

二分就完事了

import java.util.Scanner;

public class Main {


    public static long process(long cur, long n) {
        long sum = cur;
        while (cur > 0) {
            sum += cur / 10;
            cur /= 10;
        }
        return sum;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long l = 0;
        long r = n;
        while (l <= r) {
            long mid = l + (r - l) / 2;
            if (process(mid, n) == n) {
                System.out.println(mid);
                return;
            } else if (process(mid, n) > n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(-1);
    }
}

评论区一堆堆的是二分法，菜鸡的我是真的么想出来...面壁中 .....
孤零零地在找规律，最后发现如果 sum为xyzhjk，那么原数可能为xyzhjk-xyzhj  只是可能哈
至于确实是不是，那还得检查；如果不是，那还得继续判断sum是否能被有效表示    见check函数
import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            String sum = in.nextLine();
            if(Long.parseLong(sum) >= 1 && Long.parseLong(sum) <= 9) System.out.println(Long.parseLong(sum));
            else System.out.println(helper(sum));
        }    
    }
    public static long helper(String sum){
        int j = sum.length() - 1;
        char[] cs = sum.toCharArray();
        long sumLong = Long.valueOf(sum);
        long ca = Long.valueOf(new String(cs,0,cs.length - 1));
        return check(Long.parseLong(sum),sumLong - ca);
    }
    public static long check(long sum,long v){
        long res = 0;
        char[] cs = Long.toString(v).toCharArray();
        for(int len = cs.length;len > 0;len--){
            res += Long.valueOf(new String(cs,0,len));
        }
        if(res == sum) return v;
        if(res > sum){
            while(res > sum){
                v--;
                res = 0;
                cs = Long.toString(v).toCharArray();
                for(int len = cs.length;len > 0;len--){
                    res += Long.valueOf(new String(cs,0,len));
                }
            }
            if(res == sum) return v;
            else return -1;
        }else{
            while(res < sum){
                v++;
                res = 0;
                cs = Long.toString(v).toCharArray();
                for(int len = cs.length;len > 0;len--){
                    res += Long.valueOf(new String(cs,0,len));
                }
            }
            if(res == sum) return v;
            else return -1;
        }
    }
}

import java.util.*;
public class Main {
    public static long MAX = (long)1e18;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long in = sc.nextLong();
        System.out.println(niuBinarySearch(in, 0, MAX));
    }

    private static long getNiuSum(long num) {
        long ans = 0;
        while (num != 0) {
            ans += num;
            num /= 10;
        }
        return ans;
    }

    private static long niuBinarySearch(long target, long fromIndex, long toIndex) {
        while (fromIndex < toIndex) {
            long mid = (fromIndex + toIndex) >> 1;
            long midNiuSum = getNiuSum(mid);
            if (midNiuSum == target) {
                return mid;
            } else if (target > midNiuSum) {
                fromIndex = mid+1;
            } else if (target < midNiuSum) {
                toIndex = mid ;
            }
        }
        return -1;
    }
}

本套3道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
using namespace std;
long long int csum(long long int num);
int main()
{
    long long int sum; cin >> sum;
    long long int start = 1, end = sum;
    while (start + 1 < end) {
        long long int  mid = start + (end - start) / 2;
        if (csum(mid) == sum) {
            cout << mid << endl;
            return 0;
        }
        else if (csum(mid) > sum) end = mid;
        else start = mid;
    }
    if (csum(start) == sum) cout << start << endl;
    else if (csum(end) == sum) cout << end << endl;
    else cout << -1 << endl;
    return 0;
}
long long int csum(long long int num)
{
    long long int result = 0;
    while (num != 0) {
        result += num;
        num /= 10;
    }
    return result;
}

***，谁能告诉我js代码怎么测试！！！！

• 直接运算是可以的，但是我觉得有必要判断下边界问题（ 请自行打上取整补丁 ）
• 假设原始值o为100x+10y+z,那么结果值t为100x+10y+z+10x+y+z,
• 当x+y+z小于10时,那么可以由t-t/10算出o，由此可推论，不论任何数字，当各个位数相加小于10时，结果都为t-t/10
• 当x+y+z大于10时，t-t/10一定是小于o的，由此可推论，最小值为t-t/10
• 那么最大值一定和x+y+z有关，大胆假设为最大值为 t- t/10 + (x+y+z)/10
• 最后的结果就是（ 由于有一定几率一定是最小值，因此不使用二分查找，话说，我也不会用啊）

  function getNum(n) {
  let start = new Date(),
      min = n - Math.floor(n / 10),
      max = min + Math.floor( [].reduce.call( n.toString(), ( t, i ) => t + +i, 0 ) / 10),
      num = -1,
      io = num => {
          let result = 0;
          while (num >= 1) {
              result += Math.floor(num);
              num /= 10;
          }
          return result;
      };
  while (min <= max) {
      io(min) === n && (num = min, min = max);
      min++;
  }
  console.log('看看找到没', num)
  console.log("所用时间", new Date() - start)
  }
  

import java.math.BigInteger;
import java.util.*;
import java.io.*;
/**
 最大值最小问题 常用思路都是二分法，这个题目更容易。反而收到了影响，我一开始没想用二分法
然后看了题解二分 那么当然会写了，但是如果没人说二分 还是不太会。看来二分我还不会去套用model

*/
public class Main{

    static long n;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        n = in.nextLong();

        long left = 0, right = Long.MAX_VALUE;
        while(left  < right){

            Long mid = (right - left) / 2 + left;
            if(check(mid) == 0){
                System.out.println(mid);
                return;
            }else if(check(mid) == 1){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        System.out.println(-1);
    }
    static int check(long x){
        long sum = 0;
        while(x != 0){
            sum += x;
            x /= 10;
        }
        if(sum == n) return 0;
        return sum < n ? 1 : -1;
    }


}

#include <stdio.h>
int main() {
    long long a,b;long long temp;long cntl;int i;
    while(scanf("%ld",&a) != EOF){
        b=a-a/10;
        for(i=0;i<18;i++){
            cntl=b+i;
                  temp=0;
                while(cntl>0)
                {
                temp+=cntl;
                cntl=cntl/10;
                }
            if(temp==a)goto out;
        }
        if(1)printf("%d\n",-1);
        else{
out:        printf("%ld\n",b+i);
        }
    }
    return 0;
}

纯净的C语言

首先根据题意可知n<=sum<=n*1.111111111...

即n<=sum<=n*10/9

n的九分之十倍附近如果模糊的话可以直接用1.2倍来保证范围的准确性

即n<=sum<=n*1.2，sum/1.2<=n<=sum

确定n的范围之后可以使用二分法搜索，最终得出结果

#include <stdio.h>

long long sum;

long long f(long long x);

int main()
{
	long long n,min,max;
	scanf("%lld",&sum);
	min = (long long)(((double)sum)/1.2);
	max = sum;
	while(min<=max)
	{
		n = (min + max) >> 1;
		if(f(n)==sum)
		{
			printf("%lld\n",n);
			return 0;
		}
		if(f(n)<sum)
			min = n + 1;
		else
			max = n - 1;
	}
	puts("-1");
	return 0;
}

long long f(long long x)
{
	long long t=0;
	while(x)
	{
		t += x;
		x /= 10;
	}
	return t;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        long sum = s.nextLong();
        int len = (sum+"").length();
        long data = sum;
		StringBuffer sb = new StringBuffer();
		long num = 0;
		for(int i=len; i >0; i--){
			long val = sum / getNum(i);
			sb.append(val);
			num = num + val * getNum(i);
			sum %= getNum(i);
		}
        if(Long.parseLong(sb.toString()) > data){
            System.out.println(-1);
        }else{
            System.out.println(sb.toString());
        }
	}
	public static Long getNum(int n){
		StringBuffer sb = new StringBuffer();
		while(n-- >0){
			sb.append("1");
		}
		return Long.parseLong(sb.toString());
	}
}

// 二分法，最后low=middle+1；
//这样才保证不会出现low=3，high=4一直平均为3，一直low<high 而跳不出来

import java.util.*;
public class Main{
  public static void main(String[] args){
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){
                Cal(sc);
            }
        }
        public static void Cal(Scanner sc){
            String nn=sc.next();
            long n=Long.parseLong(nn);
            long low=0;
            long high=n;
            long middle=(low+high)/2;
            while(high>low) {
                long a=res(middle);
                if (a==n) {
                    System.out.println(middle);
                    return ;
                }
                if(a>n) {
                    high=middle;
                }
                else {
                    low=middle+1;
                }
    //            middle=(low+high)/2;
                middle= (low + high) >> 1;
            }
            System.out.println(-1);
        }
        public static long res(long n) {
                long sum=0;
                while(n!=0){
                    sum=sum+n;
                    n=n/10;
                }
                return sum;
        }
}

#include<stdio.h>
int main()
{
    long long sum,i,t;
    scanf("%lld",&sum);
    for(i=0;i<sum;i++)
    {
        long long s = 0;
        t = i;
        while(t)
        {
            s+=t;
            t/=10;
        }
        if(s==sum){printf("%lld",i);return 0;}
    }
    printf("-1");
}