分贝壳

//二分查找
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;
}

可以帮忙看下为什么通不过吗

m = int(input())
l, r = 0, m//10
while l < r:
    mid = l + (r - l)//2
    cnt = 0
    n = m   
    while n > 0:
        cnt += min(mid, n)
        n -= min(mid, n)
        n -= n//10
    if cnt >= m//2:
        r = mid
    else:
        l = mid + 1
print(l)

通过一个函数来计算妞妞分到的个数，并用二分查找。

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