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

lyxqqq1 · 2025-10-18 13:39:24 · 题解

题目大意

有 n 台打印机，第 i 台打印机每 t_i 秒打印一份试题，但每次打印 l_i 份试题后要休息 w_i 秒。 如果所有打印机同时工作，打印 k 份题至少要多久。

思路

• 二分答案 x，计算每台打印机在 x 秒内能打印多少试题。
• 看加起来是否大于等于 k。最差情况下，k = t_i = w_i = 109，l_i = 1，所以二分上界是2 × 1018。
• 然而 x = 2 × 1018 时，如果打印机每 1 秒打印一份题。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,t[100005],pi[100005],li[100005],w[100005];
bool ck(int x)
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int op=x/((t[i]*li[i])+w[i]);
        int res=x-(op*((t[i]*li[i])+w[i]));
        if(res/t[i]>li[i])
            ans+=op*li[i]+li[i];
        else
            ans+=(op*li[i])+res/t[i];
        if(ans>=k)
            return 1;
    }
    return (ans>=k);
}
void so()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>t[i]>>li[i]>>w[i],pi[i]=t[i]*li[i]+w[i];
    int l=0,r=LLONG_MAX,ans=0;
    while(l<=r)
    {
        int M=(l+r)/2;
        if(ck(M))
        {
            ans=M;
            r=M-1;
        }
        else
            l=M+1;
    }
    cout<<ans<<endl;
}
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        so();
    }
    return 0;
}

AC 记录