T1 包裹快递
题目描述
一个快递公司要将 \(n\) 个包裹分别送到 \(n\) 个地方，并分配给邮递员小 K 一个事先设定好的路线，小 K 需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小 K 得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。
为了节省燃料，小 K 希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。
算法描述
对于这种最大值最小或者最小值最大的问题而言，一定是二分答案，但是这个二分答案怎么写？还是没有那么明确的。
刚开始我想的是定义F[N][5]，找到所有的速度，i有早晚，i-1也有早晚，这样能形成4个时间，1表示早早，2表示早晚，3表示晚早，4表示晚晚，这样我能找到所有的速度，然后我把速度排序，在排序数组里面二分，但是我发现一个大的问题是，我不会使用sort对二维数组排序，所以后面我把所有形成的速度放在一个数组里面，在这个数组里面二分
关键部分
还有一个问题是，没能有效的利用题目提到的信息，我们二分的是速度，同时我们有距离，就能得到一个时间，那么得到的时间怎么利用呢？我们把这个时间有一个前缀和，同时和题目的信息结合起来，如果前缀和比最早的时间早，那么让他等于最早的时间，如果前缀和比最晚的时间晚，那么返回false，那么这样check函数就写好了，我认为这个部分还是比较难的，当时我是没想出来
还有一个问题？
答案是在我建立的F数组里面吗？我在数组里面二分是错误的，这个问题我还没想明白
二分部分
我们设定最小速度为0，最大速度是一个非常大的值，因为速度是小数，所以这个是在实数域上的二分。李昱东的书上讲，实数域上的二分的精度应该要比答案低一些，所以二分的过程中，我设定的精度为0.0001。
注意
这个题得开long double，开double是不行的，至于为什么？我也不太清楚，题解是这么说的
核心代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,s[maxn],t[maxn],jl[maxn],cnt;
bool check(long double x){
long double sum=0;
for(int i=1;i<=n;i++){
long double tt=jl[i]/x;//t表示的是通过这段距离的最短时间
sum+=tt;
if(sum>t[i]) return false;
if(sum<s[i]) sum=s[i];
}
return true;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&s[i],&t[i],&jl[i]);
}
long double l=0,r=1000000000,mid;
while(r-l>0.0001){
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+0.0001;
}
printf("%.2Lf",l);
return 0;
}
/**
9
4 6 3
12 19 12
18 26 6
20 29 18
27 32 4
28 36 6
29 33 13
37 40 2
49 50 3
*/