牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.
例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.
牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.
输入包括正整数sum(1 ≤ sum ≤ 10^18)
输出一个正整数,即满足条件的X,如果没有这样的X,输出-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; } }
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; } } }