爱吃喵粮的小招喵

http://www.nowcoder.com/questionTerminal/336d00e600f8496287d0d472678da774

题目难度：二星
考察点：二分查找

方法1：暴力

1.分析：

这个题目的题意有点乱，我们仔细梳理一下，其实就有n堆猫粮，小猫需要吃H小时，它每小时最多吃K粒，如果某一堆在一小时内没有吃完，那么下一个小时就继续吃；如果某一堆在一小时之内不够吃，它也不能吃别的了，然后输出一个在H小时之内吃完全部猫粮的最小的K 。其实这个题我们考虑一种暴力的情况，直接将K从1开始枚举m，如果某个K满足条件（K小时之内吃完全部猫粮），那么此时的K一定就是最小的，我们输出就可以了。我们该如何计算某个K是不是符合条件呢？其实可以这样做，假设有n堆猫粮，第i堆猫粮有a[i]粒，那么就可以遍历所有猫粮，对于第i堆猫粮计算需要吃的小时数，计算方法为如果a[i]%K==0，那么结果等于a[i]/k，否则结果等于a[i]/k+1，那么我们将这n堆猫粮所耗费的时间计算出来，假设为ans，判断ans是否小于等于H，如果满足条件，那么此时的K就是符合条件的输出即可。

算法实现：
(1). 需要处理一下输入，得到数组a和H。
(2). 写一个判断当前k是否满足条件的函数，实现方法就如上面所述。

(3).开始while(1)，K从1开始进行枚举，如果满足条件，就break。

(4). 输出第一个满足条件的K。

2.复杂度分析：

时间复杂度：O(max(a[i]))
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int a[MAXN];
int n = 0, H;
bool check(int x) {
    int ans = 0;
    for(int i=0; i<n; i++) ans += (a[i]%x)?a[i]/x+1:a[i]/x;
    return ans <= H;
}
int main() {
    while(cin>>a[n++]);
    n--; H = a[n-1]; n--;
    int ans = 1;
    while(1) {
        if(check(ans)) {
            cout<<ans<<endl;
            break;
        }
        ans++;
    }
    return 0;
}

方法2：二分

1.分析：

由于这个题的数据比较水，所以上面的方法也是可以通过的，但是显然上面的方法不是最优的，那么我们来考虑一个更优的算法，只要是查找就少不了考虑二分，所以接下来我就用二分的思想来解这道题，如果想用二分的话，首先来确定一下二分的范围，即最大值和最小值，显然最大值就是max(a[i])，那么最小值是什么呢？从理论上来说，最小值就是sum(a[i])/H（这是理论值），所以我们就在这两个范围内二分这个进食速度就可以了，其实就是求一个lower_bound，因为判断条件已经在方法1中描述完毕了，剩下的就是枚举中间值，二分就可以了。

算法实现：
(1). 还是需要处理一下输入，得到数组a和H；
(2). 写一个判断当前k是否满足条件的函数，实现方法就如上面方法1中所述；

(3). 进行二分，最小值为sum / H，最大值为max(a[i])；

(4). 输出二分之后的结果。

2.复杂度分析：

时间复杂度：O(nlog(n))
空间复杂度：O(n)

3.代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int a[MAXN];
int n = 0, H;
bool check(int x) {
    int ans = 0;
    for(int i=0; i<n; i++) ans += (a[i]%x)?a[i]/x+1:a[i]/x;
    return ans <= H;
}
int main() {
    while(cin>>a[n++]);
    n--; H = a[n-1]; n--;
    int l = 1, r = 1, sum = 0;
    for(int i=0; i<n; i++) {
        r = max(r, a[i]);
        sum += a[i];
    }
    l = sum / H;
    while(l <= r) {
        int m = (l + r) >> 1;
        if(check(m)){
            if(!check(m-1)) {
                l = m;
                break;
            }
            r = m-1;
        }
        else l = m + 1;
    }
    cout<<l<<endl;
    return 0;
}