自动搬运

查看原文

来自洛谷，原作者为

	Autream 读书和抽大麻没有区别，都是捧着死掉的植物产生幻觉。

搬运于2025-08-24 22:20:39，当前版本为作者最后更新于2024-03-03 20:20:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

有两种猴子，第一种会摘椰子，第二种会开椰子。

摘椰子的猴子有 $n$ 只，需要先用 $a_i$ 秒找椰子，再用 $b_i$ 秒摘椰子。

开椰子的猴子有 $m$ 只，需要先用 $c_i$ 秒找工具，再用 $d_i$ 秒开椰子。

现给你一个正整数 $t$，为摘椰子的猴子与开椰子的猴子所用的时间和，求在什么时候开的椰子数量等于摘的椰子的数量。

题目分析

首先观察数据范围：$1 \leq t \leq 1 \times 10^9$，枚举不行，考虑二分答案。

枚举“开的椰子数量等于摘的椰子的数量”的时刻 $x$。

直接模拟过程，最后判断开的椰子和摘的椰子大小关系即可。

bool check(int x){
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){//n只猴子同时进行，记录每只猴子开的数量
		if(x>=a[i]){
			cnt1+=(x-a[i])/b[i]+1;//使用a[i]的时间找椰子，剩余(x-a[i])的时间每b[i]秒开一个
		}
	}
	for(int i=1;i<=m;i++){
		if(t>=x+c[i]){//摘椰子用了x秒
			cnt2+=(t-x-c[i])/d[i]+1;//使用c[i]的时间找工具，剩余(t-x-c[i])的时间每d[i]秒开一个
		}
	}
	return cnt1-cnt2>0;//摘的椰子>开的椰子
}