题解：AT_joi2022ho_b 自習 (Self Study)

cyntmeay · 2025-11-04 17:36:20 · 题解

思路灵感：

如果有最小值最大或者最大值最小这些话一般都可以想到二分答案。

思路

每一个学生有两种学习的方法，第一种是自己学习，第二种是老师教。我们在最后统计答案的时候判断哪一种方法更优即可。

如何判断答案是否合法？我们将剩下的时间去学习用处不大的学科，如果可以补充完整说明时间足够理解程度也可以尝试更大的值，否则降低要求满足时间的要求。

证明二分单调性

如果当前答案不合法那么更大的答案一定也不合法，因为时间是一样的。

给出关键代码

bool check(int z){//z是二分到的答案
    int s=0;
    for(int i=1; i<=n; i++){//计算需要耗费的时间
        if(a[i]*m>=z){
            s+=(z+a[i]-1)/a[i];
        }
        else{
            s+=(z-a[i]*m+b[i]-1)/b[i]+m;
        }
    }
    if(s<=n*m){//如果时间合法增大答案
        return true;
    }
    else{
        return false;//否则尝试更小的答案知道时间满足条件
    }
}