hiho一下第65周《Highway》题目分析

45
12

题意分析

给定一条单行道的高速公路，汽车都是从坐标0，向坐标无穷移动。又因为是单行道，所以后面的车无法超越前面的车。在时刻0时，有 N 辆车同时进入这条单行道，第i辆车从坐标x[i]进入，并且将会从坐标y[i]处驶出(保证y[i]>x[i])。在行驶过程中，汽车总会保持尽可能快的速度行驶，且第i辆车的最大速度为v[i]。问每辆车离开高速公路的所花费的时间。

算法分析

刚拿到本题，相信最开始的想法都会是计算追及问题。然而若从这个角度去考虑的话，这题会变得非常复杂。因此我们必须要使用题目的一些特殊的性质。

根据题目的描述，该条高速公路为单行道，无法超车，我们可以有：

对于任意两辆车i,j，若x[i]<x[j]，则车i始终在车j之后。

那么这个性质有什么用呢？


首先第一点：

在前面的汽车始终不受后面的汽车影响。

也就是说，最前面的一辆车一定不受任何车影响，所以x[i]最大的车一定是按自己最大速度行驶到y[i]。

然后我们在考虑第二辆车时，因为第一辆车的情况我们已经清楚，所以第二辆车也就比较容易计算。

依次类推，我们若按照汽车从前往后的顺序进行处理，考虑的因素会比较少一点。

所以我们读入数据之后要做的第一件事是根据x[i]进行排序。再根据x[i]从大到小进行处理。


就算是优化了处理顺序，追及问题仍然很麻烦。对于第i辆车，我们要考虑在它离开单行道，会追上多少辆车，光是想想就觉得头疼。

所以我们必须要考虑其他的途径，这里我们需要用到不能超车这个条件产生的第二的性质：

对于道路上任意一点k，两辆车i,j，若车i在车j前，则车j经过该点的时间一定大于等于车i经过该点的时间。

我们举个例子来说明：

|---c---c---|--->
    j   i   k

其结果会有3种：

  • 车i到达k点时，车j仍未追上i

    |---c---|c------>
    j   ki

    显然车j还要再经过一段时间才能到达k，那么i经过k的时间一定小于j。

  • 车i到达k点时，车j刚好追上i

    |------|cc------>
       kji

    显然车j和车i同时到达k，那么i经过k的时间等于j

  • 车i到达k点前，车j就已经追上i

    |---cc------|--->
    ji      k

    这种情况下，车j的最大速度显然大于车i。但是车j不能超过车i，当车j追上车i时，就以和车i同样的速度前进。那么他们通过k点时间一定是相同的。

三种情况下，车j经过点k的时间都是大于等于车i的。

同理我们可以将这个情况扩展：

对于多个车来说，最后一个车经过某个点的时间一定大于或等于前面的车经过该点时间的最大值。

得到的这个性质又有什么用呢？我们仍然用一个例子来说明：

-----c-----c-----|-----|----->
     j     i    y[i]  y[j]

我们首先根据这个性质，先计算出i,j分别到达y[i]的时间t[i],t[j]。

若t[j]<t[i]，则表示v[j]>v[i]。但是不能够超车，所以j到达y[i]的时间最少为t[i]。所以我们得到j到达y[i]的时间为t[i]。

因为i到达y[i]就离开了，所以j从y[i]到y[j]的时间没有车阻挡，正常行驶。

在这个过程中我们对于车j的行驶分段进行了计算：

  • x[j]到y[i]：车j经过这一段的时间为max(t[i], t[j])

  • y[i]到y[j]：车j经过这一段的时间为max(t[j])

再扩展到多个车的情况：

----c-----c-----c-----|-----|-----|---->
    k     j     i    y[i]  y[j]  y[k]

对于车k，我们需要将整个过程分为3段：

  • x[k]到y[i]：车k经过这一段的时间为max(t[i], t[j], t[k])

  • y[i]到y[j]：车k经过这一段的时间为max(t[j], t[k])

  • y[j]到y[k]：车k经过这一段的时间为max(t[k])


通过这两个例子我们也就得到了一个计算某个车时间的算法：

对于车j来说，需要根据y的的情况，将其从起点到终点的路程分为x[j]~y[i],...,y[i']~y[j]若干段。

同时每一段时间的时间值为:

max(t[j], t[i] | 车i需要经过这段路 且 车i在车j前面)

而该时间值是具有传递性的。比如说存在i,j,k，x[i]>x[j]>x[k]，且他们都经过同一段路，则：

  • 对于i来说，取值为max(t[i])

  • 对于j来说，取值为max(t[i], t[j])

  • 对于k来说，取值为max(t[i], t[j], t[k])

若我们按照车从前往后的顺序来处理的话，我们维护一个t值：

  • 计算i时，取t = t[i]

  • 计算j时，取t = max(t, t[j])

  • 计算k时，取t = max(t, t[k])

因此我们需要对每一个y[i]维护一个t值，这样就可以使得计算通过每一段路的时间变为O(1)。


综上，可以得到我们的解题伪代码：

p = y  // copy array y
sort(p)    
For x[i] from large to small
    nowPosition = x[i]
    t = 0
    For j = 1 .. n
        If p[j] > x[i] Then
            t += (p[j] - nowPosition) / v[i]
            t = max(t[j], t)
            t[j] = t;            // update t
            If p[j] == y[i] Then
                ans[i] = t
                break;
            End If
        End If
    End For
End For

结果分析

本题现场只有1个人通过。该题的思维复杂度比较高，在时间很短的情况下并不容易想到正确的解题方法。

因此很多选手放弃了该题，或是利用程序骗取了一定的分数，也算是比较合理的选择。

  • gtdzx你好，按照您伪代码的逻辑实现未通过（已经更新nowLocation的情况下），求解答，谢谢

  • @van084 能否将您的实现代码贴一下。

  • 需要加一句 nowPosition = p[j]

  • 对，nowPosition要更新，作者可能笔误了

  • 感觉想法没错，但是实现了w了，请问您过了吗

  • 添加评论
  • ✖reply

15 answer(s)

0

按照楼主的伪代码编写的程序始终无法AC（老是WA），更糟的是，hihocoder不报告究竟哪个输入导致的错误。楼主能否将这道题的测试数据发一份给我研究一下？万分感谢！？@gtdzx 邮件：smfwuxiao@qq.com 或者谁能帮我分析一下我的代码哪里有问题也行，不胜感激。代码如下：

struct Car {
    int x;
    int y;
    int v;
    double t;
};

int main() {
    int n;
    cin >> n;
    vector<Car> cars;
    multimap<int, int> hp; // 按x由大到小排序
    multimap<int, int> vy; // 按y由小到大排序
    unordered_set<int> handled;
    for ( int i = 0; i < n; i++ ) {
        Car car;
        int x, y, v;
        cin >> x >> y >> v;
        car.x = x;
        car.y = y;
        car.v = v;
        car.t = 0;
        hp.insert(make_pair(-x, (int)cars.size()));
        vy.insert(make_pair(y, (int)cars.size()));
        cars.push_back(car);
    }

    for ( auto it1 = hp.begin(); it1 != hp.end(); it1++ ) {
        int i = it1->second;
        int np = cars[i].x;
        double t = 0;
        // cerr << "i=" << i << " x=" << cars[i].x << " y="
        //   << cars[i].y << " v=" << cars[i].v << endl;
        for ( auto it = vy.begin(); it != vy.end(); it++ ) {
            int j = it->second;
            int y = cars[j].y; //cerr << "\ty=" << y << endl;
            if ( y > cars[i].y ) {
                break;
            } else if ( y >= np && !handled.count(j) ) {
                t += (double)(y - np) / cars[i].v;
                t = max(cars[j].t, t);
                cars[j].t = t;
                np = y;
                if ( i == j ) {
                    cars[i].t = t;
                    handled.insert(i);
                }
            }
        }
    }

    for ( auto c : cars ) {
        cout << fixed << setprecision(2) << c.t << endl;
    }
    return 0;
}
2 
#include <vector>
#include <list>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct Node {
   double start;
   double end;
   double vmax;
   double t;
};

Node nodes[1000];
int Comp(Node * a, Node * b) {
   return a->start > b->start;
}
int Comp1(Node * a, Node * b) {
   return a->end < b->end;
}
double max(double a, double b) {
   if(a > b) return a;
   return b;
}
vector<Node *> startnodes;
vector<Node *> endnodes;
void read() {
   int num;
   scanf("%d", &num);
   int s;
   int e;
   int v;
   for(int i = 0; i < num; i++) {
       scanf("%d %d %d", &s, &e, &v);
       nodes[i].start = s;
       nodes[i].end = e;
       nodes[i].vmax = v;
       nodes[i].t = 0;
       startnodes.push_back(&nodes[i]);
       endnodes.push_back(&nodes[i]);
   }
   sort(startnodes.begin(), startnodes.end(), Comp);
   sort(endnodes.begin(), endnodes.end(), Comp1);
}
void solve() {
    for(int j = 0; j < endnodes.size(); j++) {
        double y = endnodes[j]->end;
        double tmax = 0;
        for(int i = 0; i < startnodes.size(); i++) {
            Node * node = startnodes[i];
            if(y <= node->end && node->start < y) {
                if(tmax == 0) {
                    node->t = node->t + (y - node->start) / node->vmax;
                    tmax = node->t;
                } else {
                    node->t = max(node->t + (y - node->start) / node->vmax, tmax);
                    tmax = node->t;
                }
                //更新起点
                node->start = y;
            }
        }
    }

}
void printfln() {
    for(int i = 0; i < startnodes.size(); i++) {
         printf("%.2f\n", nodes[i].t);
    }
}
int main(int argc, char* argv[])
{   read();
    solve();
    printfln();
    return 0;
}

  • 赞层主！您的code非常简洁清楚的。 只是有一点需要修改：在打印的时候，是需要按照输入顺序打印出来的。 所以，添加一个hashmap<int,Node*>来保存输入顺序是很有必要的。

  • 添加评论
  • ✖reply
0

这是我的程序

#include <vector>

include

include

include

using namespace std; struct Node { double start; double end; double vmax; double t; };

Node nodes[1000]; int Comp(Node * a, Node * b) { return a->start > b->start; } int Comp1(Node * a, Node * b) { return a->end < b->end; } double max(double a, double b) { if(a > b) return a; return b; } vector startnodes; vector endnodes; void read() { int num; scanf("%d", &num); int s; int e; int v; for(int i = 0; i < num; i++) { scanf("%d %d %d", &s, &e, &v); nodes[i].start = s; nodes[i].end = e; nodes[i].vmax = v; nodes[i].t = 0; startnodes.push_back(&nodes[i]); endnodes.push_back(&nodes[i]); } sort(startnodes.begin(), startnodes.end(), Comp); sort(endnodes.begin(), endnodes.end(), Comp1); } void solve() { for(int j = 0; j < endnodes.size(); j++) { double y = endnodes[j]->end; double tmax = 0; for(int i = 0; i < startnodes.size(); i++) { Node * node = startnodes[i]; if(y <= node->end && node->start < y) { if(tmax == 0) { node->t = node->t + (y - node->start) / node->vmax; tmax = node->t; } else { node->t = max(node->t + (y - node->start) / node->vmax, tmax); tmax = node->t; } //更新起点 node->start = y; } } }

} void printfln() { for(int i = 0; i < startnodes.size(); i++) { printf("%.2f\n", nodes[i].t); } } int main(int argc, char* argv[]) { read(); solve(); printfln(); return 0; }

0

strong text

Blockquote

  1. `

List item

`

0

我这啥问题，为啥只有90%的通过率？

include

include

include

include

include

using namespace std;

struct Car { int index; int start; int end; int maxspeed; double current_position; double current_time; int current_speed; };

struct timeandindex { int index; double time; };

struct arrivetime { int index; double time; };

bool compare1(Car left, Car right) { if (left.start < right.start)return true; else return false; }

bool compare2(timeandindex l1,timeandindex l2) { if (l1.time < l2.time)return true; else return false; }

bool compare3(arrivetime a1,arrivetime a2) { if (a1.index < a2.index)return true; else return false; }

bool compare4(timeandindex l1, timeandindex l2) { if (l1.index > l2.index)return true; else return false; } vector arrive(vector& v) { vector result1; int len = v.size(); int i = 0; for (i = 0; i < len; i++) { timeandindex a1; a1.index = i; a1.time = (v[i].end - v[i].current_position) / v[i].current_speed; result1.push_back(a1); } sort(result1.begin(), result1.end(), compare2); len = result1.size(); vector result; result.push_back(result1[0]); for (i = 1; i < len; i++)if (result1[i].time == result1[0].time)result.push_back(result1[i]); return result; }

vector pass(vector& v) { vector result1; int len = v.size(); int i = 0; if (len < 2)return result1; for (i = 0; i <= len-2; i++) { if (v[i].current_speed > v[i + 1].current_speed)//才有可能追上 { timeandindex a1; a1.index = i; a1.time = (v[i + 1].current_position - v[i].current_position) / (v[i].current_speed - v[i + 1].current_speed); result1.push_back(a1); } else continue; } if (result1.empty())return result1; sort(result1.begin(), result1.end(), compare2); len = result1.size(); vector result; result.push_back(result1[0]); for (i = 1; i < len; i++)if (result1[i].time == result1[0].time)result.push_back(result1[i]); return result; }

int main() { int n; while (cin >> n) { int i = 0; int j = 0; int k = 0; vector v1; vector v2; for (i = 1; i <= n; i++) { Car car; car.index = i; cin >> car.start >> car.end >> car.maxspeed; car.current_position = car.start; car.current_speed = car.maxspeed; car.current_time = 0; v1.push_back(car); } sort(v1.begin(), v1.end(), compare1);

    while (!v1.empty())
    {
        vector<timeandindex> t1;
        vector<timeandindex> t2;
        t1 = arrive(v1);
        t2 = pass(v1);
        if (t2.empty())//默认是arrive
        {
            int len = v1.size();
            for (i = 0; i < len; i++)
            {
                v1[i].current_position = v1[i].current_position + v1[i].current_speed*t1[0].time;
                v1[i].current_time = v1[i].current_time + t1[0].time;
            }
            sort(t1.begin(), t1.end(), compare4);
            for (j = 0; j < t1.size(); j++)
            {
                arrivetime arrive1;
                arrive1.index = v1[t1[j].index].index;
                arrive1.time = v1[t1[j].index].current_time;
                v2.push_back(arrive1);
                //删除v1[t1[j].index]
                vector<Car>::iterator it = v1.begin() + t1[j].index;
                vector<Car>::iterator last = v1.erase(it);
                if (t1[j].index > 0 && last != v1.end())
                {
                    if (v1[t1[j].index - 1].current_position < (*last).current_position)
                    {
                        v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                        for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                        {
                            if (v1[k].maxspeed <= v1[k + 1].current_speed)
                            {
                                v1[k].current_speed = v1[k].maxspeed;
                            }
                            else
                            {
                                v1[k].current_speed = v1[k + 1].current_speed;
                            }
                        }
                    }
                    else if (v1[t1[j].index - 1].current_position == (*last).current_position)
                    {
                        if (v1[t1[j].index - 1].maxspeed <= (*last).current_speed)v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                        for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                        {
                            if (v1[k].maxspeed <= v1[k + 1].current_speed)
                            {
                                v1[k].current_speed = v1[k].maxspeed;
                            }
                            else
                            {
                                v1[k].current_speed = v1[k + 1].current_speed;
                            }
                        }
                    }
                    else;
                }
                else if (t1[j].index > 0 && last == v1.end())
                {
                    v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                    for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                    {
                        if (v1[k].maxspeed <= v1[k+1].current_speed)
                        {
                            v1[k].current_speed = v1[k].maxspeed;
                        }
                        else
                        {
                            v1[k].current_speed = v1[k+1].current_speed;
                        }
                    }
                }
                else;
            }
        }
        else
        {
            if (t1[0].time < t2[0].time)//先到达
            {
                int len = v1.size();
                for (i = 0; i < len; i++)
                {
                    v1[i].current_position = v1[i].current_position + v1[i].current_speed*t1[0].time;
                    v1[i].current_time = v1[i].current_time + t1[0].time;
                }
                sort(t1.begin(), t1.end(), compare4);
                for (j = 0; j < t1.size(); j++)
                {
                    arrivetime arrive1;
                    arrive1.index = v1[t1[j].index].index;
                    arrive1.time = v1[t1[j].index].current_time;
                    v2.push_back(arrive1);
                    //删除v1[t1[j].index]
                    vector<Car>::iterator it = v1.begin() + t1[j].index;
                    vector<Car>::iterator last = v1.erase(it);
                    if (t1[j].index > 0 && last != v1.end())
                    {
                        if (v1[t1[j].index - 1].current_position < (*last).current_position)
                        {
                            v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                            for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                            {
                                if (v1[k].maxspeed <= v1[k+1].current_speed)
                                {
                                    v1[k].current_speed = v1[k].maxspeed;
                                }
                                else
                                {
                                    v1[k].current_speed = v1[k+1].current_speed;
                                }
                            }
                        }
                        else if (v1[t1[j].index - 1].current_position == (*last).current_position)
                        {
                            if (v1[t1[j].index - 1].maxspeed <= (*last).current_speed)v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                            for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                            {
                                if (v1[k].maxspeed <= v1[k + 1].current_speed)
                                {
                                    v1[k].current_speed = v1[k].maxspeed;
                                }
                                else
                                {
                                    v1[k].current_speed = v1[k + 1].current_speed;
                                }
                            }
                        }
                        else;
                    }
                    else if (t1[j].index > 0 && last == v1.end())
                    {
                        v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                        for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                        {
                            if (v1[k].maxspeed <= v1[k + 1].current_speed)
                            {
                                v1[k].current_speed = v1[k].maxspeed;
                            }
                            else
                            {
                                v1[k].current_speed = v1[k + 1].current_speed;
                            }
                        }
                    }
                    else;
                }
            }
            else if (t1[0].time > t2[0].time)//先超过
            {
                int len = v1.size();
                for (i = 0; i < len; i++)
                {
                    v1[i].current_position = v1[i].current_position + v1[i].current_speed*t2[0].time;
                    v1[i].current_time = v1[i].current_time + t2[0].time;
                }
                sort(t2.begin(), t2.end(), compare4);
                for (i = 0; i < t2.size(); i++)//更改
                {
                    if (v1[t2[i].index].current_speed > v1[t2[i].index + 1].current_speed)
                        v1[t2[i].index].current_speed = v1[t2[i].index + 1].current_speed;
                }
            }
            else//超过的同时到达。
            {
                int len = v1.size();
                for (i = 0; i < len; i++)
                {
                    v1[i].current_position = v1[i].current_position + v1[i].current_speed*t2[0].time;
                    v1[i].current_time = v1[i].current_time + t2[0].time;
                }

                sort(t2.begin(), t2.end(), compare4);
                for (i = 0; i < t2.size(); i++)
                {
                    if (v1[t2[i].index].current_speed > v1[t2[i].index + 1].current_speed)
                        v1[t2[i].index].current_speed = v1[t2[i].index + 1].current_speed;
                }
                sort(t1.begin(), t1.end(), compare4);
                for (j = 0; j < t1.size(); j++)
                {
                    arrivetime arrive1;
                    arrive1.index = v1[t1[j].index].index;
                    arrive1.time = v1[t1[j].index].current_time;
                    v2.push_back(arrive1);
                    //删除v1[t1[j].index]
                    vector<Car>::iterator it = v1.begin() + t1[j].index;
                    vector<Car>::iterator last = v1.erase(it);
                    if (t1[j].index > 0 && last != v1.end())
                    {
                        if (v1[t1[j].index - 1].current_position < (*last).current_position)
                        {
                            v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                            for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                            {
                                if (v1[k].maxspeed <= v1[k+1].current_speed)
                                {
                                    v1[k].current_speed = v1[k].maxspeed;
                                }
                                else
                                {
                                    v1[k].current_speed = v1[k+1].current_speed;
                                }
                            }
                        }
                        else if (v1[t1[j].index - 1].current_position == (*last).current_position)
                        {
                            if (v1[t1[j].index - 1].maxspeed <= (*last).current_speed)v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                            for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                            {
                                if (v1[k].maxspeed <= v1[k + 1].current_speed)
                                {
                                    v1[k].current_speed = v1[k].maxspeed;
                                }
                                else
                                {
                                    v1[k].current_speed = v1[k + 1].current_speed;
                                }
                            }
                        }
                        else;
                    }
                    else if (t1[j].index > 0 && last == v1.end())
                    {
                        v1[t1[j].index - 1].current_speed = v1[t1[j].index - 1].maxspeed;
                        for (k = t1[j].index - 2; k >= 0 && v1[k].current_position == v1[t1[j].index - 1].current_position; k--)
                        {
                            if (v1[k].maxspeed <=v1[k+1].current_speed)
                            {
                                v1[k].current_speed = v1[k].maxspeed;
                            }
                            else
                            {
                                v1[k].current_speed = v1[k+1].current_speed;
                            }
                        }
                    }
                    else;
                }

            }
        }
    }

    sort(v2.begin(), v2.end(), compare3);
    int len = v2.size();
    for (i = 0; i < len; i++)
        if (i != len - 1)cout << setiosflags(ios::fixed) << setprecision(2) << v2[i].time << endl;
        else cout << setiosflags(ios::fixed) << setprecision(2) << v2[i].time << endl;
}



return 0;

}

0

include

include

include

using namespace std; int GetString(const string& str) { int len=str.size();

vector<char> v;

char pre=NULL;//记录vector中最后一个元素 bool flag;//记录vector最后一个元素是否可以消除

for(int i=0;i 

        //可以消除最后一个元素
       {
            v.pop_back();
            if(!v.empty())
            {
                flag=false;
                pre=v.back();//更新pre
           }
           else
                pre=NULL;
       }
    }
   else
    {
       v.push_back(str[i]);
        flag=true;
        pre=str[i];
    }

}
string test(v.begin(),v.end());
    return len-v.size();

} int main() { int n; string s; cin>>n; string Insert="ABC"; while(n--) { cin>>s; int max=0; for(int i=0;imax) max=n; } } cout<

}

    return 0;

}

1

import java.util.Arrays; import java.util.Scanner;

public class Main {
public static void main(String[] args) {
    //输入存储项
    int x[], y[];
    double v[];
    //p数组是y的副本，xIns是x的副本
    int p[];
    ArrayX xIns[];
    //分别记录输出值，时间变量，每个y[]对应的time[]
    double ans[], t, time[];
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextInt()) {
        int n = sc.nextInt();
        //初始化
        x = new int[n];
        y = new int[n];
        v = new double[n];
        p = new int[n];
        time = new double[n];
        xIns = new ArrayX[n];
        ans = new double[n];
        //读取数据
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            v[i] = sc.nextDouble();
        }
        //复制x,y数组
        System.arraycopy(y, 0, p, 0, y.length);
        for (int i = 0; i < n; i++) {
            ArrayX arrayX = new ArrayX();
            arrayX.x = x[i];
            arrayX.index = i;
            xIns[i] = arrayX;
        }
        //对x的副本进行排序，记录变化前的位置信息
        Msort(xIns);
        //对y的副本进行排序
        Arrays.sort(p);
        for (int i = xIns.length - 1; i >= 0; i--) {
            int index = 0, nowPo = 0;
            //记录的index
            index = xIns[i].index;
            nowPo = x[index];
            t = 0;
            for (int j = 0; j < p.length; j++) {
                if (p[j] > x[index]) {
                    t += (p[j] - nowPo) / v[index];
                    nowPo = p[j];//更新nowPosition
                    t = t > time[j] ? t : time[j];
                    time[j] = t;
                    if (p[j] == y[index]) {
                        ans[index] = t;
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            //输出保留两位小数
            System.out.println(String.format("%.2f", ans[i]));
        }

    }
}

/**
 * 对ArrayX数组升序排序
 *
 * @param xIns
 */
private static void Msort(ArrayX[] xIns) {
    for (int i = 0; i < xIns.length - 1; i++) {
        for (int j = i; j < xIns.length; j++) {
            if (xIns[i].x > xIns[j].x) {
                ArrayX temp = xIns[j];
                xIns[j] = xIns[i];
                xIns[i] = temp;
            }
        }
    }
}

}

/** * 声明一个新的class * 用来给x[]数组排序，并且记录它的转换后的下标 */

class ArrayX {
public int x;
public int index;

}

0

我这个为什么只有90？

0

p = y // copy array y sort(p)
For x[i] from large to small nowPosition = x[i] t = 0 For j = 1 .. n If p[j] > x[i] Then t += (p[j] - nowPosition) / v[i] t = max(t[j], t) t[j] = t; // update t If p[j] == y[i] Then ans[i] = t break; End If End If End For End For

0

请问一下样例中最后一个时间不应该是2.83吗？为什么会是３.00

  • 最后那个车之前一直被堵，2秒的时候第一个车刚走，这个车在y=5那里，然后速度是3, 过1秒钟就到8了，一共三秒

  • 添加评论
  • ✖reply
0

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.text.DecimalFormat;

public class Main {

public static void main(String[] args) {
    int n;
    double a[][];
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    DecimalFormat df = new DecimalFormat("#.00");
    String str;
    try {
        str = br.readLine();
        n = Integer.valueOf(str).intValue();
        a = new double[n][3];
        for (int i = 0; i < n; i++){
            str = br.readLine();
            String[] numList = str.split("\\s");
            for(int j=0;j<numList.length;j++){
                a[i][j] = Double.valueOf(numList[j]).doubleValue();
            }
        }

        for (int i = 0; i < n; i++) {
            double result = (a[i][1]-a[i][0])/a[i][2];
            for (int j = 0; j < n; j++) {
                if(j!=i){
                    if(a[j][0] > a[i][0] && a[j][0] < a[i][1]){
                        double des = a[j][1]<a[i][1]?a[j][1]:a[i][1];
                        double timef = (des-a[j][0])/a[j][2];
                        double timeb = (des-a[i][0])/a[i][2];
                        double res = timeb>timef?timeb:timef;
                        if(des < a[i][1]){
                            res += (a[i][1]-des)/a[i][2];
                        }

                        if(res > result){
                            result = res;
                        }
                    }
                }
            }
            System.out.println(df.format(result));
        }
    } catch (IOException e) {
        e.printStackTrace();
    }
}

}

  • 大兄弟，你的这个程序AC了？为何我复制你这个过不了？

  • 添加评论
  • ✖reply
0

使用填表的方法按起始点的先后顺序先求出车辆经过各段路的时间，再根据前车行驶情况和当前预估时间比较，取到到该点的最大时间： static void Init() { Cars car = carHead.nextCar; int index = 0; while (car != null) { for (int position = 0; position < T; position++) {

                int start = (position == 0) ? car.start : passY[position - 1];
                if (position != 0)
                {
                    if (car.start > passY[position - 1]) start = car.start;
                }
                if (car.start <= passY[position] && passY[position] <= car.end)
                {
                    splitTime[index, position] = (float)(passY[position] - start) / car.speed;
                }
                else
                {
                    splitTime[index, position] = 0;
                }
            }
            car = car.nextCar; index++;
        }

        //更新第一个点BP
        for (int carIndex = 1; carIndex < T; carIndex++)
        {
            splitTime[carIndex, 0] = Math.Max(splitTime[carIndex, 0], splitTime[carIndex - 1, 0]);
        }
        //累加第1辆车进过各点的最小时间和
        for (int position = 1; position < T; position++)
        {
            splitTime[0, position] += (float)splitTime[0, position - 1];
        }
        for (int carindex = 1; carindex < T; carindex++)
        {
            for (int position = 1; position < T; position++)
            {
                float eTime = splitTime[carindex, position] + splitTime[carindex, position - 1];
                splitTime[carindex, position] = Math.Max(eTime, splitTime[carindex - 1, position]);
            }
        }
    }

  • 嗯，好像是跟这个有关系，我稍微改了一下成60了，谢谢启发

  • 添加评论
  • ✖reply
0

大家知道50分是怎么一回事吗

  • 我是起始位置判定错误，后来改了之后AC了 int start = (position == 0) ? car.start : passY[position - 1]; if (position != 0) { if (car.start > passY[position - 1]) start = car.start; }

  • 什么起始位置

  • 添加评论
  • ✖reply
1

p = y // copy array y sort(p) For x[i] from large to small nowPosition = x[i] t = 0 For j = 1 .. n If p[j] > x[i] Then t += (p[j] - nowPosition) / v[i] t = max(t[j], t) t[j] = t; // update t If p[j] == y[i] Then ans[i] = t break; End If End If End For End For

0

p = y // copy array y sort(p)
For x[i] from large to small nowPosition = x[i] t = 0 For j = 1 .. n If p[j] > x[i] Then t += (p[j] - nowPosition) / v[i] t = max(t[j], t) t[j] = t; // update t If p[j] == y[i] Then ans[i] = t break; End If End If End For End For

write answer 切换为英文 切换为中文

转发分享

▲