专栏文章

题解：AT_joi2022ho_b 自習 (Self Study)

ccyntmeay
AT_joi2022ho_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindrwc3
此快照首次捕获于
2025/12/02 00:45
3 个月前
此快照最后确认于
2025/12/02 00:45
3 个月前
查看原文

思路灵感：

如果有最小值最大或者最大值最小这些话一般都可以想到二分答案。

思路

每一个学生有两种学习的方法，第一种是自己学习，第二种是老师教。我们在最后统计答案的时候判断哪一种方法更优即可。
如何判断答案是否合法？我们将剩下的时间去学习用处不大的学科，如果可以补充完整说明时间足够理解程度也可以尝试更大的值，否则降低要求满足时间的要求。

证明二分单调性

如果当前答案不合法那么更大的答案一定也不合法，因为时间是一样的。

给出关键代码

CPP
bool check(int z){//z是二分到的答案
	int s=0;
	for(int i=1; i<=n; i++){//计算需要耗费的时间
		if(a[i]*m>=z){
			s+=(z+a[i]-1)/a[i];
		}
		else{
			s+=(z-a[i]*m+b[i]-1)/b[i]+m;
		}
	}
	if(s<=n*m){//如果时间合法增大答案
		return true;
	}
	else{
		return false;//否则尝试更小的答案知道时间满足条件
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...