题解 | #分石子#

分石子

http://www.nowcoder.com/practice/1ea5b4eaeff841a4918931791b000756

题意整理：

题目以数组a给出n个正整数，可以对一个整数进行操作使其拆分为两个正整数，拆分得到的两个正整数之和为原本的正整数，求得使分隔完成后存在m个正整数时，这些正整数中的最小值的最大可以取得多少。其中 $n\leq m \leq \sum a$ 由于m比所有数字总和小，所以保证了题目有解，既极端情况下将所有数字都拆分为1，得到的数字数必然不小于m

方法一：枚举

核心思想：

很明显，拆分后的最小值在区间 $[1, m i n (a [i])]$ 中。首先，拆分只能够使得数字减小，所以最终得到的最小值不会大于当前数组最小值；其次，在题意整理中已经得到最小值一定存在，且下确界为1.

另外，最小值的可能取值存在单调性，也即如果一个数字 $k\in [1,min(a[i])]$ 能够满足条件，那么所有小于k的数都能够满足条件，这是显然的，拆分得到更小的数只需要通过将一个数字的一部分分隔到另一部分即可。依赖这种性质，可以通过一种简单的算法，既从当前数组的最小值向下枚举，枚举到第一个满足条件的值即为答案。枚举过程中通过检查以当前值为最小值能否满足m个数字即可。具体过程可以见下图演示 alt

核心代码：

class Solution {
public:
    bool check(vector<int>& a, long long m, int p) {
        //检查当最小值为p时能否满足m个石子堆
        for(int i : a) {
            m -= (i / p);
        }
        return m <= 0;
    }
    int solve(int n, long long m, vector<int>& a) {
        int tmin = INT_MAX;//取得当前数组最小值
        for(int i : a) {
            tmin = min(tmin, i);
        }
        //从最小值到1，第一个满足条件的就是答案
        for(int i = tmin; i >= 1; --i) {
            if(check(a, m, i)) {
                return i;
            }
        }
        return 0;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ 。for循环开销为 $O (n)$ ，循环中每次检查开销为 $O (n)$ ，总开销为 $O (n^{2})$

空间复杂度： $O (1)$ ,只使用了常数个变量

方法二：二分查找

核心思想：

分析方法一，我们知道答案存在一种存在的单调性，既一个值成立，那么小于它的值都成立，一个值不成立，那么所有大于它的值更不可能成立，利用这种性质，可以对答案可能的范围进行二分查找，更快速的找到答案。

核心代码：

class Solution {
public:
    bool check(vector<int>& a, long long m, int p) {
        //检查当最小值为p时能否满足m个石子堆
        for(int i : a) {
            m -= (i / p);
        }
        return m <= 0;
    }
    int solve(int n, long long m, vector<int>& a) {
        int tmin = INT_MAX;//取得当前数组最小值
        for(int i : a) {
            tmin = min(tmin, i);
        }
        int i = 1, mid = 0, ans = 0;
        //二分查找答案
        while(i <= tmin) {
            mid = (i + tmin) / 2;
            if(check(a, m, mid)) {
                ans = mid;//记录答案
                i = mid + 1;
            } else {
                tmin = mid - 1;
            }
        }
        return ans;
    }
};