T266276 [NMOI-J 2022] 神の贪婪 题解

题目描述#

本题来源：力扣-875. 爱吃香蕉的珂珂 ↗ 这个神秘空间不算很大，里面有份作业,第份作业中有张试卷。

虽然现在嫉妒之神在嫉妒傲慢之神没有时间把守这个神秘空间，但是小时之后傲慢之神就会去吃饭，因为傲慢之神的吃饭时间太长，嫉妒之神不愿继续浪费时间对牛弹琴了，所以就会在小时后回到神秘空间继续把守。

因为该空间的掌控者是嫉妒之神，若嫉妒之神回来之前徵御铉还没有离开，那么到时候想离开就得耗费空间之神的大量神力,而这里的作业也因为被施加了神力而无法带走，于是徵御铉只能在这个神秘空间里卷。

徵御铉特别享受写作业的过程，所以就算他可以以接近光速的速度写完该份作业中全部的试卷，但是他希望自己写作业的速度尽可能的慢。

每写完一份作业，如果时间不满一小时，那么他会用这个小时剩下的时间来回味数学题的美好~~~~

虽然空间之神已经算到了以什么速度（单位:张试卷/小时）写作业既能使自己不消耗神力，也能使这个最小来享受写作业的感觉并且写完全部作业，但是按照风俗，他需要象征性的”向你求助”。

简化题意#

有份作业,求一个最小的速度，使得徵御铉的写完全部作业的时间小于等于小时,写试卷的每份作业的时间若不满小时，则按照小时计算，若无论取何值都无法满足条件,输出""。

输入格式#

第一行两个正整数 ,意义见上文。

第二行个非负整数，表示第份作业中有张试卷

输出格式#

一个整数，若无法满足条件，输出

样例 #1#

样例输入 #1#

4 8
3 6 7 11

样例输出 #1#

4

样例 #2#

样例输入 #2#

5 5
30 11 23 4 20

样例输出 #2#

30

样例 #3#

样例输入 #3#

5 6
30 11 23 4 20

样例输出 #3#

23

提示#

数据范围：

分析题意#

简单的二分 满足两个条件：

1. 速度最慢
2. 在个小时内做完

细节处理#

对于作业量小于的情况，无需特殊处理，向上取整即可

上代码#

#include<iostream>
#include<cmath>
using namespace std;
int a[10004],n,h,l=1,r=0,mid,t=0;
signed main(){
    cin>>n>>h;
    if(n>h){
        cout<<-1;
        return 0;
    }
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        r=r>a[i]? r:a[i];
    }
    while(l<r){
        t=0;
        mid=(l+r)>>1;
        for(int i = 1;i<=n;i++) t+=ceil(1.0*a[i]/mid);
        if(t<=h) r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}