专栏文章

【NOIP Round #6】重生

llkjzyd20
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhad0z
此快照首次捕获于
2025/12/02 02:24
3 个月前
此快照最后确认于
2025/12/02 02:24
3 个月前
查看原文
https://pjudge.ac/contest/1390/problem/21793
为什么要按照 dd 排序？（不需要！！！）
注意到题目中：你可以认为在最后一条命之前你并不能做任务，只能对任务进行思考，而在最后一条命既可以思考也可以做任务。
首先二分答案 LL 这一步是肯定要做的，考虑更显然的贪心，我们对于每一个 tit_i，肯定是能深度思考就深度思考，那么这样花的天数需要 ⌈tidi⌉\big \lceil \cfrac{t_i}{d_i} \big \rceil，但是我们考虑 L−1L-1 天的时间用来深度思考还没消掉的，对这类不满足的任务会剩余 max⁡(0,ti−L⋅di)\max(0,t_i-L\cdot d_i) 天，这种天数只能用在最后一天。然后在最后一条命上对该任务我们会选择再深度思考一次，我们统计这两种天数。
对于 checkcheck 的判断，最后一天的两种天数是否大于我们的 cc 以及深度思考的天数加上这种剩余的天数是否大于 L⋅cL\cdot c。
注意一些细节：我们二分的答案最大可能是 n×max⁡(ti)≤2×1014n\times \max(t_i)\le 2\times 10^{14}，然后天数最大可能是 c≤109c\le 10^9，那么 L⋅cL\cdot c 最大可能 ≤1023\le 10^{23}，嗯开 __int128 判断一下即可（本人傻逼一样写了半个小时高精度突然想到这个东西乐）。
给出 check 函数
CPP
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;
};

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...