首页 > 试题广场 >

乘坐公交

[编程题]乘坐公交

热度指数：4944 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

从小明家所在公交站出发有n路公交到公司，现给出每路公交的停站数(不包括起点和终点)，及每次停的时间(一路车在每个站停的时间相同)和发车的间隔，先假定每辆车同时在相对时间0分开始发车，且所有车在相邻两个站之间的耗时相同,都为5分钟。给定小明起床的相对时间(相对0的分钟数)，请计算他最早到达公司的相对时间。

给定每路车的停站数stops,停站时间period,发车间隔interval及公交路数n，出发时间s。请返回最早到达时间。保证公交路数小于等于500，停站数小于等于50。

算法知识视频讲解

C/C++

cycleof

//精简版
class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        int firsttime = INT32_MAX;
        for(int i=0;i<n;i++){
            int sd,total;
            (s%interval[i] == 0)?(sd = s):(sd = interval[i]*(s/interval[i] + 1) );
            total = sd + stops[i] * (5 + period[i]);
            if(total<firsttime)
                firsttime = total;
        }
        return firsttime+5;
    }
};
//
class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        int firsttime = 100000000;
        for(int i=0;i<n;i++){
            int sc;
            (s%interval[i]==0)?(sc = s):(sc = (s/interval[i]+1)*interval[i]);
            int tc = period[i]*stops[i];
            int xc = (stops[i]+1)*5;
            int total = sc + tc + xc;
            if(total<firsttime)
                firsttime = total;
        }
        return firsttime;
    }
};

编辑于 2017-07-15 18:30:31 回复(0)

pein531

中间不能换公交车，直接计算n路公交车的最早到达时间，然后取最小的。

等车时间：如果s%interval=0，表示出发的时候刚好来车，不用等车，否则需要等车interval-s%interval分钟。

停站时间：一共stops站，每站停period分钟，一共停stops*period分钟。

行车时间：最后一站不用听，一共有stops+1段路程要行驶，每段路程5分钟，一共(stops+1)*5分钟。

以上时间加起来再加上出发时间，就是某一路车到公司的最早时间。

import java.util.*;

public class TakeBuses {
    public int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        // write code here
        int minCost = Integer.MAX_VALUE;
        // 计算每路公交的最早到达时间，取其中最小的
        for(int i = 0; i < n; i++){
            int waitTime = s % interval[i] == 0? 0: interval[i] - s % interval[i];   // 等车时间
            minCost = Math.min(minCost, waitTime + (stops[i] + 1)*5 + stops[i]*period[i]);
        }
        return minCost + s;
    }
}

发表于 2021-04-09 23:28:15 回复(0)

VagrantYang

还是挺简单的题，可以进一步优化，即保存每辆车的坐车时间，不必每次都要去算公共项，你可以试试，我的代码没有实现

package com.special.first;

import java.util.Scanner;

/**
 * 去哪儿网02-乘公交车
 *
 * 一开始以为要换乘等等，动态规划吗？
 * 后来发现原来坐一辆车就直接到了，所以我们重点判断每辆车到公司的时间即可
 *
 * 到公司的总时间：起床时间 + 等车时间 + 坐车时间（运行时间 + 停车时间）
 *
 * 等车时间为 ：
 * 1.若起床时间正好等于发车间隔的整数倍，说明可以直接上车，等车时间为0
 * 2.若起床时间与发车间隔的取余m不为0，说明与上一辆错过了m时间
 * 同时下一辆距离发车时间为发车间隔 - m
 *
 * 坐车时间：
 * RUN_TIME * (stops[i] + 1) + period[i] * stops[i]);
 * 
 * Create by Special on 2018/3/3 11:37
 */
public class Pro033 {

    static final int RUN_TIME = 5;

    public static int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        int time = Integer.MAX_VALUE, missTime;
        for(int i = 0; i < n; i++){
            missTime = s % interval[i];
            time = Math.min(time,
                           (missTime == 0 ? 0 : interval[i] - missTime)
                                   + RUN_TIME * (stops[i] + 1)
                                   + period[i] * stops[i]);
        }
        return time + s;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int s = input.nextInt();
            int[] stops = new int[n];
            int[] period = new int[n];
            int[] interval = new int[n];
            for(int i = 0; i < n; i++){
                stops[i] = input.nextInt();
                period[i] = input.nextInt();
                interval[i] = input.nextInt();
            }
            System.out.println(chooseLine(stops, period, interval, n, s));
        }
    }
}

发表于 2018-03-03 12:03:06 回复(0)

C/C++

nbgao

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        int Min = INT_MAX;
        for(int i=0;i<n;i++)
        {
            int m = s%interval[i];
            int w;             if(m==0)
                w = 0;
            else
                w = interval[i] - m;
            Min = min(Min, w+(stops[i]+1)*5 + stops[i]*period[i]);         }         return Min + s;
    }
};

发表于 2017-10-31 01:41:32 回复(0)

zy在路上

class TakeBuses {
public:
int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
int sum,sum1,min;
min=(stops[0]+1)*5+period[0]*stops[0]+s+interval[0];
for(int i=0;i<n;i++)
{
sum1=(stops[i]+1)*5+period[i]*stops[i]+s;
if(s%interval[i]==0)
sum=sum1;
else
sum=sum1+interval[i]-s%interval[i];
if(sum<min)
min=sum;

}
    return min;
}

};

发表于 2017-07-23 10:38:10 回复(0)

Aurora1

#第一个站台没有停车时间，只有发车时间
class TakeBuses:
    def chooseLine(self, stops, period, interval, n, s):
        m = 1 << 31
        for i in range(n):
            d = s % interval[i]
            t = (0 if not d else interval[i] - d) + stops[i] * (5 + period[i])
            m = t if t < m else m
        return m + s + 5

发表于 2017-06-10 22:11:27 回复(0)

rs勿忘初心

首先vector<int> name;vector容器在这里的功能相当于一个数组，具体定义可以自己查下。这个题目解题思路是求多种路线下最短时间，公交路线n和小明出发时间s是固定的，不同的是每条公交路线的停站数stops，停站时间period，发车时间间隔interval。总时间=出发时间（s）+等车时间（WaitTime）+公交运行时间（BusTime ）。

如果小明出发的时间s刚好是发车时间间隔interval的整数倍，说明等车时间为0，什么意思？因为相对时间都是从0开始计算，例如如果第i 条发车时间间隔为30，小明出发时间60，则说明不用等车，直接坐第二趟车。

公交运行时间（BusTime ）=行驶时间+停站时间。注意行驶时间为（stops+1）*5，为什么加1，自己画画就知道了，除去起点和终点， stops 个站行驶（stops+1）段距离，停车时间=停站数（stops）*5。代码如下：

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        // write code here
        int WaitTime[n],BusTime[n],Time[n];
        int MinTime=65535;
        for(int i=0;i<n;i++)
           {
            if(s%interval[i]==0) 
              {
                WaitTime[i]=0;
              }
            else
              {
                WaitTime[i]=interval[i]-s%interval[i];
              }
                BusTime[i]=(stops[i]+1)*5+period[i]*stops[i];
                Time[i]=s+WaitTime[i]+BusTime[i];
            if(Time[i]<MinTime)
                MinTime=Time[i];
           }
        return MinTime ;
    }
};

编辑于 2017-04-18 22:16:44 回复(0)

击水3千

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        int min=1000;
        for(int i=0;i<n;++i){
            int wait=s%interval[i]?interval[i]-s%interval[i]:0;
            int t=(1+stops[i])*5+stops[i]*period[i]+s+wait;
            min=min>t?t:min;
        }
        return min;
   }
};

发表于 2017-02-25 13:48:51 回复(0)

已注销

此题的贪心体现在何处，完全一数学计算。还是我对贪心理解不够。

难道比较各次到达时间取最小就是贪心？

发表于 2017-02-15 21:09:26 回复(0)

Alex-大伟

public static int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        // write code here
		int minTime = Integer.MAX_VALUE;
		for(int i=0;i<n;i++){
			int waitCarTime = s%interval[i] == 0 ? 0 : interval[i] - s%interval[i];
			minTime = Math.min(minTime, waitCarTime + (stops[i] + 1)*5 + stops[i]*period[i]);
		}
		return minTime + s;
}

发表于 2016-09-23 16:55:44 回复(0)

wsxoo

class TakeBuses {
public:
    
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        // write code here
    	int tmpSChuI;
        int minTime=10000;
        int tmpTime;
        for(int i=0;i<n;i++){
            //这个是计算小明最快时间上车所经过的发车间隔的个数
            tmpSChuI = (0 == s%interval[i])?s/interval[i]:s/interval[i]+1;
            //这个是计算小明多久才能到公司
            tmpTime = tmpSChuI*interval[i] + stops[i]*period[i] + 5*(stops[i]+1);
            if(tmpTime<minTime){
                minTime = tmpTime;
            }
        }
        return minTime;
    }
};

发表于 2016-09-17 21:40:41 回复(0)

Glenn_Gould

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s)
    {
        vector<int> time(n);
        for(int i=0;i<n;i++)
            time[i]=stops[i]*(period[i]+5)+5+((s%interval[i])?(interval[i]-s%interval[i]):0);
        return *min_element(time.begin(),time.end())+s;
    }
};

发表于 2016-08-25 18:22:19 回复(0)

OnePiece~~

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
          int min=100000;
     	  for(int i=0;i<n;i++){
              int time=(stops[i]+1)*5+stops[i]*period[i];
              int j;
              for(j=0;j*interval[i]<s;j++);
              if(time+j*interval[i]<min)
                  min=time+j*interval[i];
          }
          return min;
    }
};

发表于 2016-08-16 19:56:16 回复(0)

Java

Afly

小明到达公司的时间由三部分组成：起床时间，等车时间，车的行驶时间

起床时间是固定的s。

等车时间取决于起床时间s与发车间隔interval。如果s%interval为0，则等车时间是0；否则等车时间是(interval-s%interval)。

车的行驶时间，包括停车时间与行驶时间，即 (停站数+1)*5分钟+停站数*停车时间。

取等车时间+行驶时间的最小值即可，返回时记得加上起床时间。

import java.util.*;

public class TakeBuses {
    public int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        // write code here
        int min = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int missTime = s%interval[i];
            int waitCost = missTime==0?0:interval[i]-missTime;
            min = Math.min(min,waitCost+(stops[i]+1)*5+stops[i]*period[i]);
        }
        return min+s;
    }
}

编辑于 2016-08-07 10:19:36 回复(11)

C/C++

卷积神经网络哦

总时间 = 坐上车之前的时间 + 在车上的时间
在车上的时间 = (stop数 + 1) *5 + stop数 * period停车时间
坐上车之前的时间:
若interval大于s 即人来之前第一班车已经走了需要等下一班坐上车之前的时间 = interval

若interval小于s 取s % interval的余数

余数为0：则一来车站就刚好赶上车坐上车之前的时间 = s

余数不为0：坐上车之前的时间 = s + interval - 余数

这两个可以合并

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        int sumt, min_t = 1e7;
        for(int i = 0; i < n; i++){
            sumt = stops[i]*period[i] + (stops[i] + 1)*5;
            int yushu = s % interval[i];
            if(yushu == 0) sumt += s;
            else sumt += (s + interval[i] - yushu);
            min_t = min(min_t, sumt); 
        }
        return min_t;   
    }
};

编辑于 2018-10-10 11:09:15 回复(0)

up97

为什么就只能坐一辆车呢，中途就不能下车再换辆车吗？这题目看不懂。。。有同感的吗？

编辑于 2017-07-11 19:36:26 回复(3)

苏南霖

有点小坑，以后要注意读题了，小明的起床时间固定为0，s是小明到达车站的时间，最后的结果以起床的0时为参考

import java.util.*;
//等车的时间最短+等的车用时最短
public class TakeBuses {
    public int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
        // write code here
        int wait = 0, use = 0, min = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int t = 0;
            while(t*interval[i]<s)    t++;
            wait = t*interval[i] - s;
            use = stops[i]*period[i]+5*(stops[i]+1);
            min = Math.min(wait+use,min);
        }
        return min+s;
    }
}

发表于 2021-04-10 16:30:39 回复(0)

皮蛋秀柚秋

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        // write code here

        int ans = INT_MAX;
        for(int i=0;i<n;++i)
        {
            int cur_time = 0;
            // 出发这个时间点需要坐第几趟车
            while(s>cur_time)
                cur_time+=interval[i];
            // 实际的出发时间 + 所有停站时间 + 路上走的时间
            // k个停站相当于有k+1个间隔  每个间隔5分钟
            ans = min(ans,cur_time + stops[i]*period[i]+(stops[i]+1)*5);
        }
        return ans;
    }
};

发表于 2020-04-12 01:13:46 回复(0)

Java

Beer201903051701541

import java.util.*;
 
public class TakeBuses {
    public int chooseLine(int[] stops, int[] period, int[] interval, int n, int s) {
         
        int[] min = new int[n];
        for (int i = 0; i < n; i++) {
            //路上停站时间与行车时间之和
            min[i] = stops[i] * period[i] + (stops[i] + 1)*5;
            if ( s % interval[i] == 0) {
                continue;
            }else {
                //出发等待时间
                min[i] = min[i] + interval[i] - (s % interval[i]);
            }
        }
        Arrays.sort(min);
        return min[0] + s;
          
    }
}

编辑于 2019-08-09 16:19:18 回复(0)

2019眷顾我

class TakeBuses {
public:
    int chooseLine(vector<int> stops, vector<int> period, vector<int> interval, int n, int s) {
        // write code here
        int minarrive=INT_MAX;
        int temp=0;
        for(int i=0;i<n;i++){
            temp=s/interval[i];
            if(temp*interval[i]==s){
                temp=s;
            }else
                temp=(temp+1)*interval[i];
            temp+=(stops[i]+1)*5+(stops[i]*period[i]);
            minarrive=min(minarrive,temp);
        }
        return minarrive;
    }
};

发表于 2018-11-19 10:53:32 回复(0)