自动搬运

查看原文

来自洛谷，原作者为

	sgl654321 风起雨停，天又放晴

搬运于2025-08-24 22:36:29，当前版本为作者最后更新于2022-02-25 21:41:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

题目大意

定义一个长度为 $n$ 的数组 $K$ 代表理解程度，初始值全为 $0$。

遍历 $m$ 次，每次遍历到 $i$，可以选择让 $K_i$ 增加 $A_i$，或者让任意一个数 $K_j$ 增加 $B_j$。

求遍历 $m$ 次后，数组 $K$ 中的最小值最大可以是多少。

解题思路

暴力做肯定会超时。粗略思考后或点开标签后，发现可以用二分答案加验证的做法。一般来说，求最大值最小，最小值最大一类的问题，一般都可以使用二分答案加验证的做法。

什么是二分答案加验证？就是一个问题的可行解按某种单调规律排列，只需要二分答案再进行验证，最终就可以得到最优解。

本题答案最小为 $1$，最大不超过 $10^{18}$。而且预期越小，是可行解的可能性越大。所以就可以进行二分答案了。

那么二分答案之后怎么验证呢？本题我们可以用贪心法进行验证。

贪心策略：先传入一个目标值。

如果自学比上课更好，那么就去自学，直到达到目标值为止。

如果上课比自学更好，那么看一看仅仅上课能否达到目标值。如果可以，那就尽可能少地去上课。如果达不到目标，那就先上完课，然后再尽可能少地自学。

将自学与上课的总课程数记为 $num$。如果 $num\le n\times m$，则该目标值是可行解。反之，就是不可行解。

我们就用第一个样例来举例吧！首先我们不停地二分答案，最终二分答案到了 $18$ 这个数。遍历每一个课程。

• 课程 $1$：上课的理解程度较高，所以我们优先上课。每一次上课能增加 $19$ 的理解程度，为了达到 $18$ 的理解程度，我们只需要上 $1$ 节课。
• 课程 $2$：自学的理解程度较高，我们就全部自学。每一次自学能够增加 $6$ 的理解程度，为了达到 $18$ 的理解程度， 我们要自学 $3$ 次。
• 课程 $3$：上课的理解程度较高，我们优先上课。每一次上课能够增加 $5$ 的理解程度，但即使 $3$ 周都上课，还是无法达到 $18$ 的理解程度。因此，剩下的 $3$ 的理解程度我们需要自学。每一次自学，我们都可以增加 $2$ 的理解程度，所以我们需要再自学 $2$ 次。总共上课和自学，用了 $5$ 节课。

所以，$3$ 门课我们一共使用了 $9$ 节课，刚好用完。经检验，发现没有比这个答案更大的可行解。所以，应该输出 $18$。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,l,r,ans,num,mid;
struct study{
	long long teach,self;
}a[300010];
long long lesson_num(long long target,long long eta){//eta 代表工作效率
	 //工作时间=工作总量/工作效率，向上取整
	 if(target%eta==0)return target/eta;
	 else return target/eta+1; 
}
bool check(long long target){//target 代表目标 
	num=0;//num代表达到目标所需的上课次数 
	for(int i=1;i<=n;i++){//每一门课都要到达大于等于目标的理解程度 
		if(a[i].self>a[i].teach)//自学比上课好，就绝对去自学 
			num+=lesson_num(target,a[i].self);
		else{//上课理解程度高，优先选择上课 
			if(m*a[i].teach>=target)//仅靠上课，就可以达到目标：）
				num+=lesson_num(target,a[i].teach);
			else{//不仅要上课，还要去自学才能达成目标qwq 
				num+=m;//上课的次数先计算上； 
				num+=lesson_num(target-m*a[i].teach,a[i].self); 
				//剩下的全部自学。 
			}
		}
	//一轮下来，我们就得出所需的上课次数了！
	//如果此时总上课次数已经超标，就不必计算直接返回假值。 
		if(num>n*m)return 0;
	} 
	return 1;

}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].teach);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].self);
	l=1;r=1000000000000000010;
	while(l<=r){//二分答案加验证 
		mid=(l+r)>>1;
		if(check(mid)==true){
			ans=mid;
			l=mid+1;
		}else r=mid-1;
	}
	printf("%lld\n",ans);
	return 0;
}

写在最后：管理大大求过。