包裹快递

题目描述

  一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。   为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。

输入数据

  第 1 行为一个正整数 n (n <2× 105) ，表示需要运送包裹的地点数。   下面 n 行，第 i+1 行有 3 个正整数 xi ， yi ， si ，表示按路线顺序给出第 i 个地点签收包裹的时间段为 [xi, yi] ，即最早为距出发时刻 xi ，最晚为距出发时刻 yi ，从前一个地点到达第 i 个地点距离为 si ，且保证路线中 xi 递增。   可以认为 s1 为出发的地方到第 1 个地点的距离，且出发时刻为 0 。

输出数据

 仅包括一个整数，为车的最大速度最小值，结果保留两位小数。

样例输入 3 1 2 2 6 6 2 7 8 4 样例输出 2.00

样例说明 　　第一段用1的速度在时间2到达第1个地点，第二段用0.5的速度在时间6到达第2个地点，第三段用2的速度在时间8到达第3个地点。

程序分析¹

解题目标

  本题要求我们求出的最大速度最小值 。像求最大值最小、最小值最大 这种类型的题目，我们很自然地就能想到用二分答案（一般情况）来求解。

解题思路

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

二分什么

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

当二分到一个满足条件的解时，LL , RR 该如何移动

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

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

在check函数中可以直接进行模拟送包裹，在模拟过程当中进行判断（具体见代码）

可能我们做二分题目会形成了思维定式，例如求最 大/小 值解的时候，若 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") .

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

代码

#include<iostream> #define length 100000 using namespace std; long double x[length], y[length], s[length]; int n; int judge(long double _midV) { long double accTime = 0; // sum记录进行时间 for (int i = 1; i <= n; i++) { if (accTime + s[i] / _midV > y[i]) // 若超出签收时间右端点（即来晚了），说明以此速度不可行，直接返回false return 0; if (accTime + s[i] / _midV< x[i]) // 如果小于签收时间左端点（即来早了），则等待至签收时间 accTime = x[i]; else accTime += s[i] / _midV; //加上到达下个地点的时间 } return 1; //若至始至终没有迟到，则说明以此速度的方案可行 } int main(void){ int i; long double lb = 0, ub = 99999999, mid; cin >> n; for (i = 1; i <= n; i++){ cin >> x[i] >> y[i] >> s[i]; } while (ub - lb >= 1e-6){ // 二分控制精度 mid = (lb + ub) / 2; if (judge(mid)) ub = mid; else lb = mid; } printf("%.2Lf\n", ub); //保留两位小数 return 0; }

---

https://www.luogu.org/problemnew/solution/P1542 ↩︎