【解题报告】 洛谷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

1
2
3
4
3
1 2 2
6 6 2
7 8 4

输出 #1

1
2.00

说明/提示

对于20%的数据，n≤10n \le 10；

对于30%的数据xi,yi,xi≤1000x_i,y_i,x_i\le 1000

对于50%的数据，n≤1000n\leq1000

对于100%的数据,n≤200000,xi≤yi≤108,si≤107n\le 200000,x_i\le y_i\le 10^8,s_i \le 10^7

时限1s

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

思路

二分

看到这道题，有一个关键词,最大速度最小，这样我们就像想到了二分的方法，并且速度越大，当然可以所有都送达，所以这里要找的是一个临界点的问题符合单调性，所以更加确定的使用了二分的方法。

大概思路就是设置一个check函数，参数为这个最大速度的最小VminV_{min}然后对于时间进行模拟，如果在某个包裹要求的时间之前达到了这个包裹的地点（将原来的总时间加上路程/速度），当然就是要等到这个时间，直接把总时间aa变成这个地点的包裹时间，如果总时间aa大于这个包裹的末时间，也就是说这个包裹没有送成功，当然是不符合答案的，所以直接返回false，在最后，如果所有的包裹都能送达，返回一个true，表示这个最小的速度肯定是小于等于当前的速度mid的，所以计算左区间有没有答案，然后如果返回的是false的话，说明这个mid还不够大，连包裹都不能在规定的时间内送到，当然速度要更大，所以计算右区间，这样就能找到一个刚刚好的值使最大速度最小。

这道题还需要注意的是double的精度只有16位（包括小数），如果整数部分过大的话将会舍弃小数部分的精度，所以我们要使用long double ，在输出的时候要用 %Lf这个L一定要是大写的，否则输出的还是double精度的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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\n",ans);
	return 0;
}