首页 > 代码库 > 包裹快递 题解

包裹快递 题解

包裹快递

【问题描述】

一个快递公司要将n个包裹分别送到n个地方,并分配给邮递员小K一个事先设定好的路线,小K需要开车按照路线给的地点顺序相继送达,且不能遗漏一个地点。小K得到每个地方可以签收的时间段,并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段,则必须在这个地方停留至可以签收,但不能晚于签收的时间段,可以认为签收的过程是瞬间完成的。

  为了节省燃料,小K希望在全部送达的情况下,车的最大速度越小越好,就找到了你给他设计一种方案,并求出车的最大速度最小是多少。

【输入格式】

输入文件express.in的第1行为一个正整数n,表示需要运送包裹的地点数。

  下面n行,第i+1行有3个正整数xi,yi,si,表示按路线顺序给出第i个地点签收包裹的时间段为[xi, yi],即最早为距出发时刻xi,最晚为距出发时刻yi,从前一个地点到达第i个地点距离为si,且保证路线中xi递增。

  可以认为s1为出发的地方到第1个地点的距离,且出发时刻为0。

【输出格式】

输出文件express.out仅包括一个数,为车的最大速度最小值,结果保留两位小数。

【输入样例】

3

  1 2 2

  6 6 2

  7 8 4

【输出样例】

    2.00

【样例解释】

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

【数据范围】

对于20%的数据,n≤10;

  对于30%的数据,xi,yi,si≤1000。

  对于50%的数据,n≤1000;

  对于100%的数据,n≤200000;xi≤yi≤108;si≤107

———————————————分割线———————————————

二分答案即可,有一个数据会神奇的卡精度,long double用可以避免。

技术分享
 1 #include "cstdio" 2 #include "algorithm" 3  4 using namespace std ; 5 const double eps = 1e-4 ; 6 const int maxN = 100100 ; 7 const double MaxNum = 1e8 + 1e-4 ; 8   9 int X [ maxN ] , Y[ maxN ] , S[ maxN ] ;10 int N ; 11 12 int INPUT ( ) {13     int x = 0 , f = 1 ; char ch = getchar ( ) ;14     while ( ch <0 || ch >9 ) { if ( ch ==-)f = -1 ; ch = getchar ( ) ; }15     while ( ch >= 0 && ch <= 9 ){ x = ( x << 1 ) + ( x << 3 ) + ch - 0 ; ch = getchar ( ) ; } 16     return x * f ; 17 }18 19 bool Check( long double ans_ )20 {21     long double ti = 0;22     for(int i = 1; i <= N; i++)23     {24         ti += (long double) S[ i ] / ans_;25         if ( ti > Y[ i ] ) return false;26         if ( ti < X[ i ] ) ti = X[ i ] ;27     }28     return true;29 }30 31 int main ( ) {32     ;33     freopen ( "express.in" , "r" , stdin ) ;freopen ( "express.out" , "w" , stdout ) ;34     N = INPUT ( ) ;35     for ( int i=1 ; i<=N ; ++i ) {36         X[ i ] = INPUT ( ) ;37         Y[ i ] = INPUT ( ) ;38         S[ i ] = INPUT ( ) ;  39     }40     long double r  = MaxNum , l = 0.0000 ;41     while ( r - l >= eps ) {42         long double mid = ( r + l ) / 2.0000 ;43         if ( Check ( mid ) ) r = mid ;44         else l = mid + eps ;45     }46     double Ans = l ; 47     printf ( "%.2lf" , Ans ) ;48     fclose ( stdin ) ;49     fclose ( stdout ) ;50     return 0 ; 51 }
View Code

2016-10-17 22:56:05 

包裹快递 题解