题目大意
一条单向的高速公路上有N辆车，在0时刻，每辆车分别在起点A[0],A[1]....处开始从北向南出发，每辆车有个终点B[0],B[1]....且每辆车有个限制速度 V[0],V[1]... 路上不能超车，即车X可能因为速度较慢，会挡住后面的车Y，但车X到达它的终点之后就消失了，不会再阻挡后面的车。 求出每辆车到达各自终点的最短时间。题目见
题目分析
此题采用模拟的方法来解决，对于每辆车都有一个终点，题目也需要我们求出每辆车到达它的终点的最短时间。但是在车行进的过程中，可能会由于其他车的阻挡而无法始终以最大速度行进，这需要我们知道每辆车在什么时间段可以最大速度行进，什么时间段只能紧贴着前车行进。这样来解决就比较麻烦，可以转换一下： （1）由于车道为单向，因此后车不会对前面的车产生影响，而后车受到前面车的影响。因此将车按照起始位置进行排序，然后按照从前向后的顺序确定每辆车到达其终点的顺序。 （2）因为考虑车A时，车A前面的车会对车A造成影响，而且影响会在前面的某车B到达车B的终点之后结束。因此，所有车的终点，都应该被视为一个重要因素，所以，保存车A前面的所有车到达车A前面的那些所有终点的时间。 （3）再考虑一下，发现不需要保存A前面所有车B1,B2...到达A前面所有终点Fi, Fi+1....的时间。我们先对A前面的终点排序，从A出发到达那些终点肯定是按照从近到远的顺序到达。我们按照模拟的方法，从近到远分阶段考察A到达Fi,Fi+1,Fi+2..的时间，考虑A从Fj到Fj+1的时间，因为考虑A之前，已经获得了A前面的那些车到达Fj+1的时间，此时，我们需要知道的是A前面的那些车到达Fj的最大的时间M，若A以全速从Fj到达Fj+1的时间（记录的是从A的起点到达Fj+1的时间)大于M，则说明A的速度不够，否则说明A的前面的车阻挡A。两种情况下，更新M，以及A到达Fj+1的时间。当A到达其终点A.end的时候，就记录A到达的时间，该时间就是A到达的最短时间。
所以，只需要记录每个终点有车到达的最大的时间即可。
实现（c++）
#define _CRT_SECURE_NO_WARNINGS #include#include #include using namespace std;#define MAX_CAR_NUM 1005/*此题采用模拟的方法来解决，对于每辆车都有一个终点，题目也需要我们求出每辆车到达它的终点的最短时间。但是在车行进的过程中，可能会由于其他车的阻挡而无法始终以最大速度行进，这需要我们知道每辆车在什么时间段可以最大速度行进，什么时间段只能紧贴着前车行进。这样来解决就比较麻烦，可以转换一下：（1）由于车道为单向，因此后车不会对前面的车产生影响，而后车受到前面车的影响。因此将车按照起始位置进行排序，然后按照从前向后的顺序确定每辆车到达其终点的顺序。（2）因为考虑车A时，车A前面的车会对车A造成影响，而且影响会在前面的某车B到达车B的终点之后结束。因此，所有车的终点，都应该被视为一个重要因素，所以，保存车A前面的所有车到达车A前面的那些所有终点的时间。（3）再考虑一下，发现不需要保存A前面所有车B1,B2...到达A前面所有终点Fi, Fi+1....的时间。我们先对A前面的终点排序，从A出发到达那些终点肯定是按照从近到远的顺序到达。我们按照模拟的方法，从近到远分阶段考察A到达Fi, Fi+1,Fi+2..的时间，考虑A从Fj到Fj+1的时间，因为考虑A之前，已经获得了A前面的那些车到达Fj+1的时间，此时，我们需要知道的是A前面的那些车到达Fj的最大的时间M，若A以全速从Fj到达Fj+1的时间（记录的是从A的起点到达Fj+1的时间)大于M，则说明A的速度不够，否则说明A的前面的车阻挡A。两种情况下，更新 M，以及A到达Fj+1的时间。当A到达其终点A.end的时候，就记录A到达的时间，该时间就是A到达的最短时间。所以，只需要记录每个终点有车到达的最大的时间即可。*/int gEndPoint[MAX_CAR_NUM]; //保存各个终点的位置double gMaxEndTime[MAX_CAR_NUM];int gCarIndex[MAX_CAR_NUM];struct Car{ int start_point; int end_point; int end_index; double v_limit; double arrive_time;};Car gCars[MAX_CAR_NUM];//用于对车的索引按照车的起点位置排序，bool Compare1(int index1, int index2){ return gCars[index1].start_point < gCars[index2].start_point;}//根据车A的起点，找到车A需要经过的那些终点的起始序号（终点经过排序）int GetEndIndex(int start, int n){ int beg = 0, end = n; while (beg < end){ int mid = (beg + end) / 2; if (gEndPoint[mid] == start) return mid; else if (gEndPoint[mid] > start) end = mid; else beg = mid + 1; } return beg;}int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d %d %lf", &gCars[i].start_point, &gCars[i].end_point, &gCars[i].v_limit); gEndPoint[i] = gCars[i].end_point; gCarIndex[i] = i; } memset(gMaxEndTime, 0, sizeof(gMaxEndTime)); //对车的索引排序 gCarIndex[0]表示起点最小的车在gCar中的位置，gCarIndex[1]表示起点第二小的车在gCar中的位置 sort(gCarIndex, gCarIndex + n, Compare1); //对终点进行排序 sort(gEndPoint, gEndPoint + n); for (int i = 0; i < n; i++){ gCars[i].end_index = GetEndIndex(gCars[i].end_point, n); //二分法确定车的终点序号，用于当车到达终点时记录 } //从前向后考虑 for (int i = n - 1; i >= 0; i--){ int start_index = GetEndIndex(gCars[gCarIndex[i]].start_point, n); double time = 0, point = gCars[gCarIndex[i]].start_point, v_limit = gCars[gCarIndex[i]].v_limit; //考察车A的路程经过的那些终点即可 for (int index = start_index; index <= gCars[gCarIndex[i]].end_index; index++){ if (time + (gEndPoint[index] - point) / v_limit > gMaxEndTime[index]){ //判断是否前车阻挡 time += (gEndPoint[index] - point) / v_limit; gMaxEndTime[index] = time; } else{ time = gMaxEndTime[index]; } if (gCars[gCarIndex[i]].end_index == index){//到达终点进行更新 gCars[gCarIndex[i]].arrive_time = gMaxEndTime[index]; } point = gEndPoint[index]; } } for (int i = 0; i < n; i++){ printf("%.2lf\n", gCars[i].arrive_time); } return 0;}