【NOIP Round #6】重生

lkjzyd20 · 2025-10-27 21:28:15 · 个人记录

https://pjudge.ac/contest/1390/problem/21793

为什么要按照 d 排序？（不需要！！！）

注意到题目中：你可以认为在最后一条命之前你并不能做任务，只能对任务进行思考，而在最后一条命既可以思考也可以做任务。

首先二分答案 L 这一步是肯定要做的，考虑更显然的贪心，我们对于每一个 t_i，肯定是能深度思考就深度思考，那么这样花的天数需要 \big \lceil \cfrac{t_i}{d_i} \big \rceil，但是我们考虑 L-1 天的时间用来深度思考还没消掉的，对这类不满足的任务会剩余 \max(0,t_i-L\cdot d_i) 天，这种天数只能用在最后一天。然后在最后一条命上对该任务我们会选择再深度思考一次，我们统计这两种天数。

对于 check 的判断，最后一天的两种天数是否大于我们的 c 以及深度思考的天数加上这种剩余的天数是否大于 L\cdot c。

注意一些细节：我们二分的答案最大可能是 n\times \max(t_i)\le 2\times 10^{14}，然后天数最大可能是 c\le 10^9，那么 L\cdot c 最大可能 \le 10^{23}，嗯开 __int128 判断一下即可（本人傻逼一样写了半个小时高精度突然想到这个东西乐）。

给出 check 函数

auto check=[&](int day)->bool{
    int dep_type=0;
    int last_day=0;
    int last_dep_day=0;
    rep(i,1,n){
        int dep_solve=(t[i]+d[i]-1)/d[i];
        if(dep_solve<=day-1){
            dep_type+=dep_solve;
        }else{
            dep_type+=day;
            ++last_dep_day;
            last_day+=max(0ll,t[i]-d[i]*day);
        }
    }
    if(last_dep_day+last_day>life) return 0;
    if(last_day+dep_type>(__int128)life*day) return 0;
    return 1;
};