牛牛和妞妞去海边捡了一大袋美丽的贝壳,千辛万苦地运回家后,牛牛和妞妞打算分掉这些贝壳。
牛牛提出,他和妞妞轮流从还没有分配的贝壳中取一定数量的贝壳,直到贝壳分完为止。分配规则是牛牛每次取剩余贝壳的1/10(向下取整),妞妞每次固定取m个贝壳,妞妞先取。
妞妞想要得到不少于一半的贝壳,又不想太过分,那么她一次最少取多少个贝壳才能得到不少于一半的贝壳呢?
一个正整数n,表示贝壳的总数量,1<=n<=1000000000000000000。
一个正整数m,表示妞妞一次最少取的贝壳数量。
10
1
70
3
使用二分查找下界的思想。
将mid作为妞妞一次拿多少的值
如果当前的mid满足“妞妞想要得到不少于一半的贝壳”,
则记录下当前mid的值,并继续向左查找。
否则就是mid值太小,向右查找
public class 分贝壳 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in); long n = input.nextLong(); long start = 1; long end = n; long temp = 0; while (start < end) { long mid = start+(end-start)/2; if (minNum(mid,n)) { temp = mid; end = mid; }else { start = mid+1; } } System.out.println(temp); } private static boolean minNum(long m,long n) { //m为妞妞一次拿多少,n为贝克总数 long num1 = 0; //妞妞拿的贝壳数long temp = n; //剩下的贝壳总数 long mid = 0; while (temp>=0) { if (temp < m) { num1 += temp; break; } num1 += m; temp -= m; temp -= temp/10; } if (n%2 == 0) mid = n/2; else mid = (n+1)/2; return num1>=mid?true:false; } }