自动搬运

查看原文

来自洛谷，原作者为

	Koakuma 你不能作我的诗，正如我不能做你的梦。

搬运于2025-08-24 21:26:16，当前版本为作者最后更新于2019-03-29 03:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

博客食用更佳

$Structure$

本题要求我们求出 车的最大速度最小值 。

像求 最大值最小、最小值最大 这种类型的题目，我们很自然地就能想

到用二分答案（一般情况）来求解。

$Solution$

做二分题目时，我们要弄清楚这样几点：

1. 二分什么

2. 如何判断是否可行 ( 即check函数的内容 )

3. 当二分到一个满足条件的解时，$L$ , $R$ 该如何移动

针对以上三个问题，我们来一步一步解决。

$S1.$ 题目求速度，所以我们可以直接二分最大速度的值

$S2.$ 在check函数中可以直接进行模拟送包裹，在模拟过程当中进行

判断（具体见代码）

$S3.$ 可能我们做二分题目会形成了思维定式，例如求最 大/小 值解的时

候，若 $mid$ 满足题意，则就将 $L = mid + 1$ 或将 $R = mid - 1$

然而，由于此题考虑到精度问题，如果按照上述操作，那么我们就会

错过 $1 / 0.01 = 100$（及以上）个可能满足条件的解 （保留两位小

数）。

所以正确的格式应是：

mid = (l + r) / 2;
if (check(mid)) Res = mid, r = mid;
else l = mid;

另外，由于本题数据原因对精度要求较高，所以在定义实数类型时要

用 long double ，相与之搭配的输出应是 printf("%Lf") .

到此为止，问题都已经解决。

下面给出朴实代码

$Code$

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 2e5 + 100;
using namespace std;
int x[maxn], y[maxn], s[maxn];
int N;
long double Res;
inline bool check(double k)
{
	long double sum = 0;   // sum记录进行时间
	for (int i = 1 ; i <= N ; ++i)
	{
		sum += s[i]/k;    //加上到达下个地点的时间
		if (sum > y[i]) return false; // 若超出签收时间右端点（即来晚了），说明以此速度不可行，直接返回false
		if (sum < x[i]) sum = x[i]; // 如果小于签收时间左端点（即来早了），则等待至签收时间
	}
	return true;  //若至始至终没有迟到，则说明以此速度的方案可行
}
int main()
{
	cin >> N;
	for (int i = 1 ; i <= N ; ++i)
	 scanf("%d%d%d", &x[i], &y[i], &s[i]);
	long double l, r, mid;
	l = 0, r = 1e9;
	while (r-l >= 0.00001)  // 二分控制精度
	{
		mid = (l + r) / 2;
		if (check(mid)) Res = mid, r = mid;
		else l = mid;
	}
	printf("%0.2Lf\n", Res); //保留两位小数
	
    return 0;
}

$After\ Writing$

希望此题解能让泥萌有所收获

最后感谢管理大大的审核qaq

再见~