[Luogu P1542] 包裹快递

刺骨的言语ヽ痛彻心扉 2021-10-25 11:57 266阅读 0赞

[原题链接qwq][qwq]

## \$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\$ ##

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

转载于:https://www.cnblogs.com/SuYii/p/10846989.html

[qwq]: https://www.luogu.org/problemnew/show/P1542