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

题目描述

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

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

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

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

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

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

简化题意

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

输入格式

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

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

输出格式

一个整数$m$，若无法满足条件，输出$-1$

样例 #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 \leq n \leq 10^4,1 \leq h \leq 10^9,1 \leq a_i \leq 10^9$

分析题意

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

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

细节处理

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

上代码

#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;
}