P14237 [CCPC 2024 Shandong I] 打印机 题解

SP_beyond_xxxx · 2025-10-17 18:50:25 · 题解

思路

这道题如果你想到了二分那么你可以尝试将 long long 改为 __int128 试试，我就是这样吃罚时的。

如果没有想到二分的话，我们可以从头分析。

• 看见 1 \le k \le 10^9 但 n 的数据只有可怜的 1 \le n \le 100 那么肯定是二分答案（时间），check 函数中嵌套 O(n) 循环。即可轻松解题。
• 然后就要看 check 函数究竟怎么实现。我们可以把一次打印和停机看成一组，然后看传入的时间能否支持，若支持，那么一轮可以打 l_i 份，否则就只能看剩下的时间够支持几个 t_i。
• 最后别忘了考虑不够一组但能打完 l_i 份的情况，这是仍在停机但可能把停机时间算上打印了我们可以使用三目运算符 (x%p[i]<=t[i]*l[i]?(x%p[i])/t[i]:l[i]) 其中 p_i 表示一组时间，或 min 函数 ans=min(ans,l[i]*t[i])。

代码

#include<bits/stdc++.h>
using namespace std;
__int128 T;
__int128 n,k,t[110],l[110],w[110],p[110];
bool f=0;
inline void read(__int128 &x){
    x=0;char ch;
    bool f=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
    if (ch=='-')
        f=true;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
inline void wr(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
inline bool check(__int128 x){
    __int128 ans=0;
    for(__int128 i=1;i<=n;i++){
        ans+=(x/p[i])*l[i];
        ans+=(x%p[i]<=t[i]*l[i]?(x%p[i])/t[i]:l[i]);//注意！！！ 
    }
    if(ans>=k)return 1;
    else return 0;
}
int main(){
    read(T);
    while(T--){
        read(n),read(k);
        for(__int128 i=1;i<=n;i++)read(t[i]),read(l[i]),read(w[i]),p[i]=t[i]*l[i]+w[i];
        __int128 l=0,r=1e32,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid))r=mid-1;
            else l=mid+1;
        }
        wr(l);
        puts("");
    }
    return 0;
}

之后就会发现你获得了 \textcolor{green}{Accepted}。