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

题目大意

有

n

台打印机，第

i

台打印机每

t_i

秒打印一份试题，但每次打印

l_i

份试题后要休息

w_i

秒。如果所有打印机同时工作，打印

k

份题至少要多久。

n ≤ 100,t_i, l_i,w_i, k ≤ 109

思路

二分答案 $x$ ，计算每台打印机在 $x$ 秒内能打印多少试题。
看加起来是否大于等于 $k$ 。最差情况下， $k = t_i = w_i = 109，l_i = 1$ ，所以二分上界是 $2 × 1018$ 。
然而 $x = 2 × 1018$ 时，如果打印机每 1 秒打印一份题。
$n = 100$ 台打印机一共可以打印 $2 × 1020$ 份，超出了 $long long$ 的上界。所以二分过程需要判断和已经大于 k 时提前返回 $true$ 。

AC code

CPP

#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 记录

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

文章操作

题目大意

思路

AC code

相关推荐

评论

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