首页 > 试题广场 >

最后一位

[编程题]最后一位
  • 热度指数:7232 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.
例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.
牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

输入描述:
输入包括正整数sum(1 ≤ sum ≤ 10^18)


输出描述:
输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。
示例1

输入

564

输出

509
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;
    }


}


发表于 2021-08-01 12:32:25 回复(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);
    }
}
发表于 2019-06-15 17:18:48 回复(4)
评论区一堆堆的是二分法,菜鸡的我是真的么想出来...面壁中 .....
孤零零地在找规律,最后发现如果 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;
        }
    }
}



编辑于 2019-02-10 21:54:13 回复(1)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long sum = sc.nextLong();
        long r=sum ,l=0;
        Boolean flag=false;
        while (l<(r-1)){
            long mid = (l+r)/2;
            if(getSum(mid)==sum){
                System.out.println(mid);
                flag =true;
                break;
            }else if(getSum(mid)<sum){l=mid;}
            else { r=mid;}

        }
        if (getSum(l)==sum){
            System.out.println(l);
        }
        else if(getSum(r)==sum){
            System.out.println(r);
        }
        else if(!flag){
            System.out.println(-1);
        }
    }

    private static long getSum(long a) {
        long sum=0;
        while(a!=0){
            sum+=a;
            a/=10;
        }
        return sum;
    }
}

发表于 2017-11-30 14:11:18 回复(0)