分石子

[编程题]分石子

热度指数：1370 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有n堆石子堆，第i堆一共有 $a_i$ 个石子。

牛牛可以对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。

现在牛牛需要通过分裂得到m堆石子，他想知道这m堆石子的最小值最大可以是多少？

示例1

输入

3,5,[3,5,6]

输出

说明

把5分裂成2和3
把6分裂成2和4
得到五堆石子[3,2,3,2,4]

备注:



第一个参数n代表石子堆的个数
第二个参数m表示需要得到的石子堆数。
第三个参数vector a代表每堆石子堆的石子个数

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 分石子
     * @param n int整型 
     * @param m long长整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, long long m, vector<int>& a) {
        int l=1, r=*min_element(a.begin(), a.end())+1;
        while(l+1<r){
            int mid = (l+r)>>1;
            long long k=0;
            for(auto &x: a)
                k += x/mid;
            if(k < m)
                r = mid;
            else
                l = mid;
        }
        return l;
    }
};

发表于 2020-07-28 14:41:59 回复(0)

牛客745599318号

#
# 分石子
# @param n int整型 
# @param m long长整型 
# @param a int整型一维数组 
# @return int整型
#
class Solution:
    def solve(self , n , m , a ):
        # write code here
        if n == m: return min(a)
        left, right = 1, min(a)
        
        while left<right:
            mid = (left+right+1) >> 1
            total = sum(nums//mid for nums in a)
            if total >= m:
                left = mid
            else:
                right = mid-1
        return left

发表于 2020-07-28 16:07:07 回复(0)