实时公交到站数计算

题目：XX市实时公交项目，能得到该市的公交车每一次报站信息，比如“下一站到五道口站，请下车的乘客做好准备”，需要得到线路上每个站点的下两辆车到站情况。

抽象：

131路公交车有19站，有编号为1 2 3 4，四辆公交车，四辆车下一个站点分别是2 4 6 8。那么对于1号站点，前面没有公交车，就输出-1，-1表示没有接下来的两辆车。而3号站点，因为前面只有一个1号公交车（马上到2号站台），所以输出1，-1（第一辆公交车还有1站，没有第二辆公交车）。对于18号站点，最近的两辆公交车是6、8号站台的3 4号公交车，所以输出10，12.

求demo。

#include <vector>#include <map>#include <utility>#include <cstdio>#include <algorithm>using namespace std;//一个busInfo表示车号为busNum的车下一站是pos站typedef struct{int busNum;int pos;} busInfo;//路线id到当前线路上所有车的busInfo映射static map<int,vector<busInfo>> lineInfos;//路线id到路线总站数的映射static map<int,int> stationCount;//输出每一站的接下来两辆车信息，格式为“站编号：第一辆车到此站站树，第二辆车到此站站数”，0为马上到，-1为没有车void printLineInfo(int lineNum){int nstation = stationCount[lineNum];vector<busInfo> infos = lineInfos[lineNum];for_each(infos.begin(),infos.end(),[](const busInfo &info){printf("(%d,%d) ",info.busNum,info.pos);});printf("\n");int i = 1,now = 0;//now是当前车站的下一个公交，每次循环就是看当前公交是否已经不是站点的“下一个”，然后根据“下一个”信息输出当前站点公交信息while(i <= nstation){if(i == infos[now].pos){while(now <= (infos.size() - 1) && i >= infos[now].pos)now++;}if(now == 0)printf("%d:-1,-1\n",i);else if(now == 1)printf("%d:%d,-1\n",i,i - infos[now - 1].pos);else if((now - 2) >= 0)printf("%d:%d,%d\n",i,i - infos[now - 1].pos,i - infos[now - 2].pos);elseprintf("%d:%d,-1\n",i,i - infos[now - 1].pos);i++;}printf("\n");}//车辆位置更新事件，车辆加入线路void busArrived(int lineNum,const busInfo &info){vector<busInfo> &infos = lineInfos[lineNum];int nstation = stationCount[lineNum];bool del = false;if(info.pos >= nstation)del = true;//删除之前车辆已有信息vector<busInfo>::iterator iter = find_if(infos.begin(),infos.end(),[info](const busInfo &in){return info.busNum == in.busNum;});if(iter != infos.end())infos.erase(iter);//如果是到终点站，删除后直接返回if(del)return;//否则按顺序插入infos.insert(upper_bound(infos.begin(),infos.end(),info,[](const busInfo &lhs,const busInfo &rhs){return lhs.pos <= rhs.pos;}),info);}int main(){int lineNum = 100;//100号线路有18个站点stationCount[100] = 18;//100号线路上有4辆公交，1号马上到3号站点，2号到7号...vector<busInfo> infos = {{1,3},{2,7},{7,9},{10,11}};lineInfos[100] = infos;//打印线路到站信息printLineInfo(100);lineInfos[100] = infos;//2号巴士到达第10站台busInfo info = {2,10};busArrived(100,info);//再次打印printLineInfo(100);}

输出：

(1,3) (2,7) (7,9) (10,11)

1:-1,-1

2:-1,-1

3:0,-1

4:1,-1

5:2,-1

6:3,-1

7:0,4

8:1,5

9:0,2

10:1,3

11:0,2

12:1,3

13:2,4

14:3,5

15:4,6

16:5,7

17:6,8

18:7,9

(1,3) (7,9) (2,10) (10,11)

1:-1,-1

2:-1,-1

3:0,-1

4:1,-1

5:2,-1

6:3,-1

7:4,-1

8:5,-1

9:0,6

10:0,1

11:0,1

12:1,2

13:2,3

14:3,4

15:4,5

16:5,6

17:6,7

18:7,8

符合预期