牛牛和妞妞去海边捡了一大袋美丽的贝壳,千辛万苦地运回家后,牛牛和妞妞打算分掉这些贝壳。
牛牛提出,他和妞妞轮流从还没有分配的贝壳中取一定数量的贝壳,直到贝壳分完为止。分配规则是牛牛每次取剩余贝壳的1/10(向下取整),妞妞每次固定取m个贝壳,妞妞先取。
妞妞想要得到不少于一半的贝壳,又不想太过分,那么她一次最少取多少个贝壳才能得到不少于一半的贝壳呢?
一个正整数n,表示贝壳的总数量,1<=n<=1000000000000000000。
一个正整数m,表示妞妞一次最少取的贝壳数量。
10
1
70
3
n = int(input().strip()) def f(m, n): sum_ = 0 while n > 0: if n >= m: sum_ += m n -= m else: sum_ += n n -= n if n >= 10: n -= n//10 return sum_ low, high = 1, max(1, n//10) min_mid = high min_value = float("inf") while low <= high: mid = (low + high)//2 value = f(mid, n) if value >= (n+1)//2: if value < min_value: min_value = value min_mid = mid high = mid - 1 else: low = mid + 1 print(min_mid)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(br.readLine().trim()); // 使用二分法进行查找 long left = 1, right = n / 10; long harvest = Long.MAX_VALUE, minPerTime = right; while(left <= right){ long mid = left + (right - left) /2; long nums = getShell(mid, n); if(nums >= (n + 1) / 2){ // 超过半数,满足条件,看能否更新一下最小值 if(nums < harvest){ harvest = nums; minPerTime = mid; } right = mid - 1; }else left = mid + 1; } System.out.println(minPerTime); } private static long getShell(long m, long n) { long sum = 0; while(n > 0){ if(n >= m){ // 如果还够每次拿m个就拿m个 sum += m; n -= m; }else{ // 否则就剩下多少拿多少 sum += n; n = 0; } // 大于10个的时候牛牛才有得拿 if(n >= 10) n -= n / 10; } return sum; } }
//二分查找 import java.util.Scanner; /** * @Author: coderjjp * @Date: 2020-05-09 16:28 * @Description: * @version: 1.0 */ public class Main { public static void main(String[] args) { long n = new Scanner(System.in).nextLong(); long l = 1, r = n; long mid; while (l <= r){ mid = (l + r) / 2; if (isOK(n, mid)) r = mid - 1; else l = mid + 1; } System.out.println(l); } private static boolean isOK(long n, long mid) { long count = 0; long cur = n; while (cur > 0){ if (cur <= mid){ count += cur; cur = 0; }else { count += mid; cur -= mid; } cur -= cur/10; } return count >= n/2; } }
#include<stdio.h> int main() { long long int n; scanf("%lld",&n); long long int right=n/10;//右边界 long long int left=1;//左边界 long long int m=left+(right-left)/2; int flag=0; long long int pre=0; while(1) { long long int a_get=0;//牛牛得到的贝壳 long long int b_get=0;//妞妞得到的贝壳 long long int temp=n; while(1) { temp-=m; b_get+=m; a_get+=temp/10; temp-=temp/10; if(a_get>(n+1)/2) { flag=0;//说明当前的m不够 break; } if(b_get>=(n+1)/2)//这里注意,因为是int型做除法,为了确保妞妞至少拿到一半(万一总数是奇数),所以要(n+1)/2 { flag=1;//说明当前的m够了 break; } } if(flag==0) { left=m+1;//因为m不够,所以左边界变大 if(left>right) { m=pre;//如果从这里退出循环,那么正确的m应该是pre(上一个符合条件的m) break; } m=left+(right-left)/2;//二分 } else { pre=m;//记录符合条件的m right=m-1;//因为m够了,所以右边界变小 if(left>right)//退出整个循环的条件是左边界大于右边界!注意不是大于等于!!! { break; } m=left+(right-left)/2;//二分 } } printf("%lld",m); return 0; }
#include <bits/stdc++.h> using namespace std; long long sum; inline bool check(long long x){ long long t=sum,sum1=0,sum2=0; while(t>0){ x=min(t,x); //保证x<=t; sum1+=x; t-=x; sum2+=t/10; t-=t/10; } return sum1>=sum2; } long long binary(long long left,long long right){ long long mid; while(left<=right){ mid=left+(right-left)/2; if(check(mid)==true){ if(check(mid-1)==false) return mid; right=mid-1; } else left=mid+1; } return left; } int main(){ long long len,t; cin>>sum; len=(sum/10)>>1; len=max(len,1LL); cout<<binary(1,len); return 0; }
#include <iostream> using namespace std; // 计算妞妞是否能拿到一半的贝壳 bool m_get_more_shell(long long n, long long m, long long msum, long long nsum){ if(m > n){ return msum + n >= nsum; } msum += m; nsum += (n - m)/10; long long left_shells = (n - m) - (n - m)/10; return m_get_more_shell(left_shells, m, msum, nsum); } int main() { long long n; while(cin >> n){ long long left = 0; long long right = (n + 1) / 2; while(left != right - 1){ // m取left个正好拿不到一半,m取right个正好能拿到一半 long long mid = (left + right) / 2; if(m_get_more_shell(n, mid, 0, 0)){ right = mid; } else{ left = mid; } } cout << right << endl; } return 0; }
使用二分查找下界的思想。
将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; } }
#include using namespace std; //感觉是个数学题,妞妞一次最少取的个数 bool is_cheack(int m,int n) { int female = 0; int male = 0; while(n>0){ int tmp = min(m, n); female += tmp; n -= tmp; tmp = n/10; male += tmp; n = n-tmp; } return female>=male; } int main() { int m; cin >> m; //贝壳数量 long long left = 1,right = m/2; while(left < right) { long long mid = (right -left)/2 + left; if(is_cheack(mid,m) == true) { right = mid; }else left = mid +1; } cout << left <<endl; return 0; }
可以帮忙看下为什么通不过吗
通过一个函数来计算妞妞分到的个数,并用二分查找。
from math import ceil def check_num(N,m): x1,x2 = 0,0 while N > 0: #lady first t2 = m if m <= N else N N -= t2 x2 += t2 t1 = N // 10 N -= t1 x1 += t1 return x2 N = int(input()) left,right = 1,N while left <= right : mid = (left+right)//2 x2 = check_num(N, mid) if x2 > ceil(N/2): right = mid -1 else: left = mid + 1 print(left)
#include<bits/stdc++.h> using namespace std; #define ll long long // 判定取m个时能否满足获得不少于一半的贝壳 int isOk(ll n,ll m){ ll a = 0, b = 0; while(n>0){ if(m>=n) { b+=n; n = 0; } else{ b+=m; a+=(n-m)/10; n -= (m+(n-m)/10); } } //cout<<a<<" "<<b<<endl; return b>=a; } int main() { ll n; cin>>n; ll l = 1; ll r = n; ll mid; ll ans = -1; while(l<=r){ // 二分,穷举所有可能的m mid = (l+r)>>1; //cout<<"l r :"<<l<<" "<<r<<endl; //cout<<"m:"<<mid<<endl; // 大于等于 if(isOk(n,mid)) { ans = mid; r = mid - 1; } // 小于 else l = mid + 1; } cout<<ans<<endl; return 0; }
#include<iostream> using namespace std; int check(long long m, long long all){ long long remain = all; long long get = 0; while(remain>0){ if(remain>=m){ remain -= m; get += m; remain -= remain/10; } else{ get += remain; break; } } if(get>=(all/2)) return 1; else return 0; } long long biSearch(long long head,long long end,long long all){ while(head<end){ long long mid = (head+end)/2; int flag = check(mid,all); if(flag){ end = mid; } else{ head = mid+1; } } return end; } int main(){ long long n; cin>>n; cout<<biSearch(1,n,n); }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong();//贝壳数 System.out.println(bFind(n)); } /** * 二分查找妞妞每次最少需要拿的贝壳数 * * @param shellNum 贝壳总数 * @return 妞妞每次最少需要拿的贝壳数 */ private static long bFind(long shellNum) { long l = 0; long r = shellNum / 10 + shellNum % 10; while (l < r) { long m = l + (r - l) / 2;//妞妞取的贝壳数 if (isNecessary(m, shellNum)) { r = m; } else { l = m + 1; } } return l; } /** * 判断妞妞一次取的贝壳数 <take> 是否是可行的 * * @param take 妞妞一次取的贝壳数 * @param shellNum 总共的贝壳数 * @return 妞妞取的贝壳数是否可行 */ private static boolean isNecessary(long take, long shellNum) { long leastTakeNum = shellNum / 2 + (shellNum & 1); long takeCnt = 0; while (shellNum > 0) { if (shellNum <= take) { takeCnt += shellNum; break; } else { takeCnt += take; shellNum -= take;//妞妞先取 shellNum -= shellNum / 10; } } return takeCnt >= leastTakeNum; } }
# coding: utf-8 # 二分查找 n = int(input()) def get_more_shell(m, left, n, shell_num): if left <= m: shell_num += left if shell_num > n/2: return True else: return False left -= m shell_num += m left -= left//10 return get_more_shell(m, left, n, shell_num) l_limit = 1 r_limit = max(n//10, 1) while True: if r_limit-l_limit <= 1: break mid = (l_limit+r_limit) // 2 if get_more_shell(mid, n, n, 0): r_limit = mid else: l_limit = mid print(r_limit)
#include <bits/stdc++.h> #define ll long long using namespace std; ll F(ll m, ll n){ ll s = 0; while(n>0){ if(n>=m){ s += m; n -= m; }else{ s += n; n = 0; } if(n>=10) n -= n/10; } return s; } int main(){ ll n,m,l,r; cin>>n; l = 1; r = (n<10)?1:n/10; ll Min=LONG_MAX,p=r,t; while(l<=r){ m = (l+r)/2; t = F(m,n); if(t>=(n+1)/2){ if(t<Min){ Min = t; p = m; } r = m - 1; }else l = m + 1; } cout<<p<<endl; return 0; }