【解题报告】 洛谷P1542 包裹快递
题目描述
小K成功地破解了密文。但是乘车到X国的时候，发现钱包被偷了，于是无奈之下只好作快递员来攒足路费去Orz教主……
一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。
为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。
输入格式
第1行为一个正整数n，表示需要运送包裹的地点数。
下面n行，第i+1行有3个正整数xi，yi，si，表示按路线顺序给出第i个地点签收包裹的时间段为[xi, yi]，即最早为距出发时刻xi，最晚为距出发时刻yi，从前一个地点到达第i个地点距离为si，且保证路线中xi递增。
可以认为s1为出发的地方到第1个地点的距离，且出发时刻为0。
输出格式
仅包括一个正数，为车的最大速度最小值，结果保留两位小数。
输入输出样例
输入 #1
3
1 2 2
6 6 2
7 8 4
输出 #1
2.00
说明/提示
对于20%的数据，(n le 10)；
对于30%的数据(x_i,y_i,x_ile 1000)
对于50%的数据，(nleq1000)
对于100%的数据,(nle 200000,x_ile y_ile 10^8,s_i le 10^7)
时限1s
第一段用1的速度在时间2到达第1个地点，第二段用0.5的速度在时间6到达第2个地点，第三段用2的速度在时间8到达第3个地点。
思路
二分
看到这道题，有一个关键词,最大速度最小，这样我们就像想到了二分的方法，并且速度越大，当然可以所有都送达，所以这里要找的是一个临界点的问题符合单调性，所以更加确定的使用了二分的方法。
大概思路就是设置一个check函数，参数为这个最大速度的最小(V_{min})然后对于时间进行模拟，如果在某个包裹要求的时间之前达到了这个包裹的地点（将原来的总时间加上路程/速度），当然就是要等到这个时间，直接把总时间(a)变成这个地点的包裹时间，如果总时间(a)大于这个包裹的末时间，也就是说这个包裹没有送成功，当然是不符合答案的，所以直接返回false，在最后，如果所有的包裹都能送达，返回一个true，表示这个最小的速度肯定是小于等于当前的速度mid的，所以计算左区间有没有答案，然后如果返回的是false的话，说明这个mid还不够大，连包裹都不能在规定的时间内送到，当然速度要更大，所以计算右区间，这样就能找到一个刚刚好的值使最大速度最小。
这道题还需要注意的是double的精度只有16位（包括小数），如果整数部分过大的话将会舍弃小数部分的精度，所以我们要使用long double ，在输出的时候要用 %Lf这个L一定要是大写的，否则输出的还是double精度的数字。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int MAXN=2000005;
const double eps=0.00001;
int n;
int x[MAXN],y[MAXN],s[MAXN];
long double ans;
bool check(double vmin)
{
long double a=0;//a表示已经进行的时间
for(int i=1;i<=n;i++)
{
a+=s[i]/vmin;
if(a<x[i])
a=x[i];
if(a>y[i])
return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i]>>s[i];
long double l=0,r=1e9;
while(r-l>=eps)
{
double mid=(l+r)/2;
if(check(mid)) r=mid,ans=mid;
else l=mid;
}
printf("%.2Lf
",ans);
return 0;
}