首页 > 试题广场 > 分贝壳
[编程题]分贝壳
  • 热度指数:5413 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛和妞妞去海边捡了一大袋美丽的贝壳,千辛万苦地运回家后,牛牛和妞妞打算分掉这些贝壳。
牛牛提出,他和妞妞轮流从还没有分配的贝壳中取一定数量的贝壳,直到贝壳分完为止。分配规则是牛牛每次取剩余贝壳的1/10(向下取整),妞妞每次固定取m个贝壳,妞妞先取。
妞妞想要得到不少于一半的贝壳,又不想太过分,那么她一次最少取多少个贝壳才能得到不少于一半的贝壳呢?

输入描述:
一个正整数n,表示贝壳的总数量,1<=n<=1000000000000000000。


输出描述:
一个正整数m,表示妞妞一次最少取的贝壳数量。
示例1

输入

10

输出

1
示例2

输入

70

输出

3
二分查找。不过看了下面好几个答案。右边界都太大了。由于妞妞先拿,只要妞妞同样拿1/10,那么妞妞肯定不会比牛牛少。所以右边界为n/10。
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)



发表于 2019-08-28 14:20:18 回复(2)
使用二分法进行查找,确定m后模拟分贝壳的过程,看是否能够满足获得不少于一半贝壳的要求,满足数量要求的话就看能否更新m的最小值。
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;
    }
}


发表于 2021-01-30 23:08:11 回复(0)
//二分查找
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;
    }
}

发表于 2020-05-09 17:17:17 回复(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;
}

发表于 2019-11-12 16:26:38 回复(1)
  • 使用二分查找下界的思想。

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

编辑于 2019-05-03 22:22:48 回复(1)
#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;
}

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

发表于 2020-08-06 21:37:02 回复(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)

编辑于 2020-08-05 22:07:52 回复(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)
发表于 2020-07-15 13:14:42 回复(0)
#include <stdio.h>
#include <iostream>
using namespace std;
long long int GirlGetCnt(long long int nGirlGetPerTime,long long int nTotalCnt)
{
    long long int nGirlGetCnt = 0;
    long long int nRestCnt = nTotalCnt;
    while(nRestCnt)
    {
        long long int nGirlGetThisTime = (nGirlGetPerTime < nRestCnt)?
            nGirlGetPerTime : nRestCnt;
        nGirlGetCnt += nGirlGetThisTime;
        nRestCnt -= nGirlGetThisTime;
        
        if(0 == nRestCnt)
        {
            break;
        }
        
        nRestCnt -= (long long int)(nRestCnt/10);
    }
    
    return nGirlGetCnt;
}

int main()
{
    long long int nTotal=0;
    cin >> nTotal;
    
    // 利用二分法查找,上限是n/10
    long long int nRightValue = reinterpret_cast<long long int>(nTotal/10);
    long long int nLeftValue = 1;
    long long int nHalfCnt = reinterpret_cast<long long int>(nTotal/2);
    long long int nMidValue = nRightValue;
    long long int nRetValue = nMidValue;
    while(nLeftValue <= nRightValue)
    {
        if(nHalfCnt <= GirlGetCnt(nMidValue,nTotal))
        {
            nRetValue = nMidValue;
            nRightValue = nMidValue - 1;
        }
        else
        {
            nLeftValue = nMidValue + 1;
        }
        //cout<<__LINE__<<": "<<nHalfCnt<<":"<<GirlGetCnt(nMidValue,nTotal)<<" retval:"<<
        //    nRetValue<<endl<<" left:"<<nLeftValue<<" mid:"<<nMidValue<<" right:"<<nRightValue<<endl;
        nMidValue = reinterpret_cast<long long int>((nRightValue + nLeftValue)/2);
    }
    
    cout<<nRetValue<<endl;
}
发表于 2020-07-02 00:14:44 回复(0)
#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;
}
发表于 2020-06-06 00:29:58 回复(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);
}

发表于 2020-06-03 10:08:21 回复(0)
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;
    }

}

发表于 2020-04-05 18:35:20 回复(1)
不错的哈
发表于 2020-03-04 20:17:39 回复(0)
#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;
 } 

发表于 2020-03-03 18:51:46 回复(2)
# 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)

发表于 2019-09-04 17:06:59 回复(0)
#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;
}

发表于 2019-09-03 14:08:49 回复(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;
}

发表于 2019-06-26 15:05:22 回复(1)
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<stdio.h>
#include<list>
没有学过ACM,果然,不用二分查找,复杂度过大;
using namespace std;

bool minmax(int n,int m)
{   int remain=n;
    int a=0;
    while(m<remain)
    {
        a+=m;
        remain-=m;
        remain=remain-remain/10;
    }
    a+=remain;
    return a>=n/2;
}
int main(){
    long long n;
    cin>>n;
    long left=1,right=n;
    long middle=1+(right-left)/2;
    
    while(minmax(n,middle))
    {
       middle-=1;
    }
    cout<<middle+1<<endl;
}
    
发表于 2019-05-08 11:36:17 回复(2)