自动搬运

查看原文

来自洛谷，原作者为

	MA_tian 除了狗运，我看不见其它

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

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

以下是正文

这题测试点是真的多

题目大意

有 $n$ 条道路，第 $i$ 公路长 $l_i$ 米，限速为 $v_i$ 米，超速就要按照给定规则分段罚款，每辆车从 $s_i$ 时刻开始行驶，$v_i$时刻离开公路。求最小的最大罚款金额。

思路

最小的最大，一眼二分答案。

不知道二分的建议先搞懂这题。

这题与二分模版不同的是，你需要先计算经过公路的时间，然后再对罚款范围进行二分。

代码

代码中的变量名意义与题目相同。

#include<bits/stdc++.h>
using namespace std;
int n,m,q,s,t,v[100005],l[100005],a[100005],f[100005];
bool check(int p){
	double use=0;//利用double变量保留精度
	for(int i=1;i<=n;i++){
		use+=l[i]/(v[i]+p);
	}
	return use+s<=t;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	for(int i=1;i<=n;i++){
		cin>>l[i];
	}
	cin>>m;
	for(int i=1;i<m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>f[i];
	}
	cin>>q;
	while(q--){
		int l=0,r=m-1,mid;
		cin>>s>>t;
		while(l<r){
			mid=l+(r-l)/2;
			if(check(a[mid])){
				r=mid;
			}else{
				l=mid+1;
			}
		}
		if(!check(a[l])){
			l++;
		}
		cout<<f[l]<<endl;
	}
	return 0;
}

此题完结撒花！

夹带点私货

满堂花醉三千客，一剑霜寒十四州。