首页 > 试题广场 >

赶去公司

[编程题]赶去公司
  • 热度指数:4845 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
终于到周末啦!小易走在市区的街道上准备找朋友聚会,突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域,每条街道假设坐标是(X,Y),小易当前在(0,0)街道,办公室在(gx,gy)街道上。小易周围有多个出租车打车点,小易赶去办公室有两种选择,一种就是走路去公司,另外一种就是走到一个出租车打车点,然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间,打车将花费taxiTime时间。小易需要尽快赶到公司去,现在小易想知道他最快需要花费多少时间去公司。

输入描述:
输入数据包括五行:
第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)
第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔


输出描述:
输出一个整数表示,小易最快能赶到办公室的时间
示例1

输入

2 -2 -2 0 -2 -4 -2 15 3

输出

42
//
//  main.cpp
//  violent_enumeration
//
//  Created by LU QI on 2017/11/06.
//  Copyright © 2017 LU QI. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int spend(int x1,int y1,int x2,int y2,int Time){
    int spend = abs(x1-x2)+abs(y1-y2);
    spend *= Time;
    return spend;
}
int main(int argc, const char * argv[]) {
    int n,gx,gy,walkTime,taxiTime,t1,t2,t;
    cin>>n;
    int tx[n],ty[n];
    for(int i=0;i<n;i++){
        cin>>tx[i];
    }
    for(int i=0;i<n;i++){
        cin>>ty[i];
    }
    cin>>gx>>gy>>walkTime>>taxiTime;
    t = spend(tx[0], ty[0], 0, 0, walkTime)+spend(tx[0],ty[0],gx,gy,taxiTime);
    for(int i=1;i<n;i++){
        t1 = spend(tx[i],ty[i],0,0,walkTime);
        t2 = spend(tx[i],ty[i],gx,gy,taxiTime);
        if(t>t1+t2){
            t = t1+t2;
        }
    }
    int f = spend(0,0,gx,gy,walkTime);
    t = t>f?f:t;
    cout<<t<<endl;
    return 0;
}



发表于 2017-11-08 13:22:07 回复(0)
更多回答
第一眼看到题目以为是图的题。。。原来这么简单
package go.jacob.day913;

import java.util.Scanner;

public class Demo1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] X = new int[n];
		int[] Y = new int[n];
		for (int i = 0; i < n; i++) {
			X[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			Y[i] = sc.nextInt();
		}
		int gx = sc.nextInt(), gy = sc.nextInt();
		int walkTime = sc.nextInt(), taxiTime = sc.nextInt();

		int min = walkTime * (Math.abs(gx) + Math.abs(gy));
		for (int i = 0; i < n; i++) {
			int tmp = walkTime * (Math.abs(X[i]) + Math.abs(Y[i]))
					+ taxiTime * (Math.abs(gx - X[i]) + Math.abs(gy - Y[i]));
			if (tmp < min)
				min = tmp;
		}
		System.out.println(min);
		sc.close();
	}
} 


发表于 2017-09-13 09:58:44 回复(0)
import java.util.*;
//该题目比较简单,针对两种不同的方式计算即可
//1. 完全走步
//2. 先走到停车点,之后坐车到达
public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
    	//获得出租车打车点
    	int Tcount = scanner.nextInt();
    	int [] txArray = new int[Tcount];
    	int [] tyArray = new int[Tcount];
    	//初始化出租车打车点的x坐标
    	for(int i = 0;i < Tcount;i++){
        	txArray[i] = scanner.nextInt();
    	}
    	//初始化出租车打车点的Y坐标
    	for(int j  = 0;j < Tcount;j++){
        tyArray[j] = scanner.nextInt();
    	}
    	//得到目的地地址
    	int gx = scanner.nextInt();
    	int gy = scanner.nextInt();
    	//得到走路时间和打车时间
    	int walkTime  = scanner.nextInt();
    	int taxiTime  = scanner.nextInt();
    
    	//完全走路所需要的时间
    	int totalByWalk = (Math.abs(gx)+ Math.abs(gy)) * walkTime;
    	//保存打车所费时间的最小值
    	int totalByTaxi = Integer.MAX_VALUE;
    	//对于打车
    	for(int k = 0;k < Tcount;k++){
        	//走到停车点的时间
        	int firstTime = (Math.abs(txArray[k])+Math.abs(tyArray[k])) * walkTime;
        	//坐车到目的地时间
        	int secondTime = (Math.abs(txArray[k]- gx) + Math.abs(tyArray[k]- gy)) * taxiTime;
        
        	totalByTaxi = Math.min(totalByTaxi,firstTime + secondTime);
    	}
    	System.out.println(Math.min(totalByWalk,totalByTaxi));
    }
}

发表于 2017-08-10 10:31:52 回复(0)
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int tx[] = new int[n];
		int ty[] = new int[n];
		for (int i = 0; i < n; i++) {
			tx[i] = sc.nextInt();//打车点x坐标
		}
		for (int i = 0; i < n; i++) {
			ty[i] = sc.nextInt();//打车点y坐标
		}
		int gx = sc.nextInt();//公司x坐标
		int gy = sc.nextInt();//公司y坐标

		int wt = sc.nextInt();// 走路速度
		int dt = sc.nextInt();// 打车速度

		int walkTime = (Math.abs(gx) + Math.abs(gy)) * wt;// 如果全部走路
		int driveTime = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {// 如果打车
			driveTime = Math.min(driveTime,
					(Math.abs(ty[i]) + Math.abs(tx[i])) * wt + (Math.abs(ty[i]-gy)+Math.abs(tx[i]-gx)) * dt);
		}
		System.out.println(Math.min(driveTime, walkTime));
	}
}

发表于 2017-04-04 23:00:06 回复(6)
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
intWal, Tex;
 
intgetT(intx, inty, intrx, intry){
// 计算走到车站的时间
    intwa = (abs(x)+abs(y))*Wal;
    // 计算车站到公司的时间
    intte = (abs(rx-x) + abs(ry-y))*Tex;
// 返回总花费时间
    returnwa+te;
}
 
// 主函数
intmain(){
    intn;
    inttx[51];
    intty[51];
    intcom[2];
    intwal, tex;
    cin >> n;
    inti=0;
    while(i!=n){
        cin>>tx[i++];
    }
    i=0;
    while(i!=n){
        cin>>ty[i++];
    }
    cin>>com[0]>>com[1];
    cin>>wal>>tex;
    Wal = wal;
    Tex = tex;
    // 直接步行的时间
    intwalktime = (abs(com[0]) + abs(com[1]))*wal;
    
    // 循环处理从每一个车站乘车去公司的时间
    intt = 2147483647;
    for(inti=0; i < n; i++){
        // 计算每一个车站乘车的总时间
        inttemp = getT(tx[i], ty[i], com[0], com[1]);
      // 判断是否是最小时间
        if(temp < t){
            t = temp;
        }
    }
    cout<<(t<walktime?t:walktime)<<endl; 
}

发表于 2017-03-25 17:31:22 回复(0)
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int tx[51];
    int ty[52];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tx[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> ty[i];
    }
    int gx, gy;
    cin >> gx >> gy;
    int walkTime, taxiTime;
    cin >> walkTime >> taxiTime;
    int walk = (abs(gx) + abs(gy)) * walkTime;
    int minTime = walk;
    for (int i = 0; i < n; i++)
    {
        double temp = 0;
        temp += (abs(tx[i]) + abs(ty[i])) * walkTime;
        temp += (abs(tx[i] - gx) + abs(ty[i] - gy))*taxiTime;
        if (temp < minTime)
            minTime = temp;
    }
    cout << minTime;
}
发表于 2020-05-28 17:38:23 回复(0)
import sys
n=int(sys.stdin.readline().strip())
x=list(map(int,sys.stdin.readline().strip().split()))
y=list(map(int,sys.stdin.readline().strip().split()))
targetx,targety=list(map(int,sys.stdin.readline().strip().split()))
walktime,taxitime=list(map(int,sys.stdin.readline().strip().split()))
result=walktime*(abs(targetx)+abs(targety))
for i in range(n):
    t1=walktime*(abs(x[i])+abs(y[i]))
    t2=taxitime*(abs(targetx-x[i])+abs(targety-y[i]))
    t=t1+t2
    if t<result:
        result=t
print(result)
发表于 2018-05-17 09:03:39 回复(0)
看不懂
发表于 2017-09-07 10:02:37 回复(0)
☠头像
### 分析
基础题,先算步行的时间,再枚举每个打车点算出打的时间,找到时间最短的即可。

### 我的答案
```cpp
#include<iostream>
#include<algorithm>
#define MAX 100000000
using namespace std;
int n;
int tx[51],ty[51];
int gx,gy;
int wt,dt;
int main(){
    cin>>n;
    int walkTime=MAX,driveTime=MAX;
    for(int i=0;i<n;i++){
        cin>>tx[i];
    }
    for(int i=0;i<n;i++){
        cin>>ty[i];
    }
    cin>>gx>>gy>>wt>>dt;
    walkTime=(abs(gx)+abs(gy))*wt;
    for(int i=0;i<n;i++){
        driveTime=min(driveTime,(abs(ty[i])+abs(tx[i]))*wt+(abs(ty[i]-gy)+abs(tx[i]-gx))*dt);
    }
    cout<<min(driveTime,walkTime)<<endl;
}
```
发表于 2017-03-31 13:08:22 回复(0)
#include <iostream>
using namespace std;

struct Point {
    int x;
    int y;
} point;

int main()
{
    int n;
    cin >> n;
    Point taxi[n];
    for ( int i = 0; i < n; i++ )
        cin >> taxi[i].x >> taxi[i].y;
    Point company;
    cin >> company.x >> company.y;
    int walkTime, taxiTime;
    cin >> walkTime >> taxiTime;

    int res = ( abs(company.x) + abs(company.y) ) * walkTime;
    int curWalk, curTaxi;
    for ( int i = 0; i < n; i++ ) {
        curWalk = ( abs(taxi[i].x) + abs(taxi[i].y) ) * walkTime;
        curTaxi = ( abs(taxi[i].x - company.x)  + abs(taxi[i].y - company.y) ) * taxiTime;
        res = min(res, (curWalk + curTaxi) );
    }

    cout << res << endl;
    return 0;
}
编辑于 2017-03-27 11:38:38 回复(3)
const timeCal = (posX, posY, offX, offY, speed) => {
    const yTime = Math.abs(offY - posY) * speed
    const xTime = Math.abs(offX - posX) * speed
    return yTime + xTime
}

const main = (taxiNum, taxiX, taxiY, officeX, officeY, walkSpeed, taxiSpeed) => {
    var time = timeCal(0, 0, officeX, officeY, walkSpeed);
    for(let i = 0; i < taxiNum; i++){
        let walkTime = timeCal(0, 0, taxiX[i], taxiY[i], walkSpeed)
        let taxiTime = timeCal(taxiX[i], taxiY[i], officeX, officeY, taxiSpeed)
        let totalTime = walkTime + taxiTime
        time = (totalTime < time)?totalTime:time
    }
    return time
}

//except: 42
console.log(main(2, [-2, 0],[-2, -2], -4, -2, 15, 3))

发表于 2020-03-26 20:31:12 回复(0)
#该题目比较简单,针对两种不同的方式计算即可
#完全走步
#先走到停车点,之后坐车到达,遍历所有停车点,不要觉得穷举就不能做
#有时候最直接的思路能解决就行
class solution():
    def timeToCompany(self,n,tx,ty,gx,gy,walkTime,taxiTime):
        n = int(n)
        tx = [int(item) for item in tx]
        ty = [int(item) for item in ty]
        gx = int(gx)
        gy = int(gy)
        walkTime = int(walkTime)
        taxiTime = int(taxiTime)

        #完全走路需要的时间如下:
        totalTimeWalk = (abs(gx)+abs(gy))*walkTime
        #遍历所有打车点,求出最小的打车时间
        totalTimeTaxi = float("inf")#保存打车所费时间的最小值
        for i in range(n):
            #走到停车点的时间
            firstTime = (abs(tx[i])+abs(ty[i]))*walkTime
            #坐车到公司的时间
            secondTime = (abs(tx[i]-gx)+abs(ty[i]-gy))*taxiTime
            totalTimeTaxi = min(totalTimeTaxi,firstTime+secondTime)
        
        print(min(totalTimeTaxi,totalTimeWalk))

if __name__ == "__main__":
    n = input()
    tx = input().split(' ')
    ty = input().split(' ')
    gx,gy = input().split(' ')
    walkTime,taxiTime = input().split(' ')
    solution().timeToCompany(n,tx,ty,gx,gy,walkTime,taxiTime)

发表于 2019-08-24 18:17:55 回复(0)
#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

#include<string>

#include<cmath>
#include<string>


using namespace std;



int main()
{
    int n;
    int tx[51],ty[51];
    int gx,gy;
    int wt,dt;
    //cin>>n;
    cin>>n;
    //int i = 0;
    for (int i = 0; i < n; i++)  //横坐标
    {
        cin>>tx[i];
        //i += 1;
    }
    //int j = 0;
    for (int j = 0; j < n; j++) //纵坐标
    {
        cin>>ty[j];
        //j += 1;
    }
   // for(int i=0;i<n;i++){
     //   cin>>tx[i];
    //}
    //for(int i=0;i<n;i++){
      //  cin>>ty[i];
    //}
    cin>>gx>>gy;
    cin>>wt>>dt;
    int OnlyWalkTime = (abs(gx) + abs(gy)) * wt;
    for (int k = 0; k < n; k++)
    {
        int MixTime = (abs(gx - tx[k]) + abs(gy - ty[k])) * dt + (abs(tx[k]) + abs(ty[k])) * wt;
        OnlyWalkTime = min(OnlyWalkTime, MixTime);
    }
    cout << OnlyWalkTime << endl;
    return 0;
}
 
发表于 2019-07-15 15:46:32 回复(0)
#include<iostream>
#include<math.h>
#include<algorithm>

using namespace std;
int main(){
    int n,i,gx,gy,wt,tt,walk2stop,stop2company;
    cin>>n;
    int arr_x[n],arr_y[n];
    for(i=0;i<n;++i) cin>>arr_x[i];
    for(i=0;i<n;++i) cin>>arr_y[i];
    cin>>gx>>gy>>wt>>tt;
    int walktime=(abs(gx)+abs(gy))*wt;
    int car_time=99999999;
    for(i=0;i<n;++i){
        walk2stop=(abs(arr_x[i])+abs(arr_y[i]))*wt;
        stop2company=(abs(gx-arr_x[i])+abs(gy-arr_y[i]))*tt;
        car_time=min(car_time,walk2stop+stop2company);
    }
    
    
    cout<<min(car_time,walktime);
    return 0;
}
发表于 2018-12-19 22:00:45 回复(0)
# 将步行,步行到打车点再打车的花费时间全部列举出来,找到最小值即可
import sys


class Solution:
    def get_arrival_time(self, arr_x, arr_y, aim, walk_speed, taxi_speed):
        cost = self.get_walk_time(aim, walk_speed)
        index = 0
        while index < len(arr_x):
            tmp_cost = self.get_taxi_time(aim, arr_x[index], arr_y[index], walk_speed, taxi_speed)
            cost = min([cost, tmp_cost])
            index += 1
        print(cost)

    def get_walk_time(self, aim, walk_speed):
        total_dis = abs(aim[0]) + abs(aim[1])
        return total_dis * walk_speed

    def get_taxi_time(self, aim, x, y, walk_speed, taxi_speed):
        walk_time = self.get_walk_time((x, y), walk_speed)
        taxi_dis = abs(aim[0]-x) + abs(aim[1]-y)
        return walk_time + taxi_dis*taxi_speed


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    arr_x = list(map(int, sys.stdin.readline().split()))
    arr_y = list(map(int, sys.stdin.readline().split()))
    aim = list(map(int, sys.stdin.readline().split()))
    w_speed, t_speed = map(int, sys.stdin.readline().split())
    solution = Solution()
    solution.get_arrival_time(arr_x, arr_y, aim, w_speed, t_speed)

发表于 2018-07-11 10:26:54 回复(0)

总是有10%的测试用例跑不过。谁能帮忙看看是哪里有问题吗?

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    int tx[n], ty[n];
    for (int i = 0; i < n; i++) {
        cin>>tx[i];
    }
    for (int i = 0; i < n; i++) {
        cin>>ty[i];
    }
    int gx, gy;
    cin>>gx>>gy;
    int walkT, taxiT;
    cin>>walkT>>taxiT;
    int totalWalkT = (abs(gx) + abs(gy)) * walkT;   //完全走去的时间

    int chosenTaxiX = 0, chosenTaxiY = 0, minLenToTaxi = 20000;
    for (int i = 0; i < n; i++) {
        int len = abs(tx[i]) + abs(ty[i]);
        if (len < minLenToTaxi) {
            minLenToTaxi = len;
            chosenTaxiX = tx[i];
            chosenTaxiY = ty[i];
        }
    }
    int lenToG = abs(gx - chosenTaxiX) + abs(gy - chosenTaxiY);
    int totalTaxiT = minLenToTaxi * walkT + lenToG * taxiT;    //打车去的时间
    cout<<(totalWalkT > totalTaxiT ? totalTaxiT : totalWalkT);
    return 0;
}
发表于 2017-10-19 17:21:32 回复(0)
package mem;

import java.util.*;

public class GoComp {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int taxNum = sc.nextInt();         int taxX[] = new int[taxNum];         int taxY[] = new int[taxNum];         for (int i = 0; i < taxNum; i++) {             taxX[i] = sc.nextInt();         }         for (int i = 0; i < taxNum; i++) {             taxY[i] = sc.nextInt();         }         int gx = sc.nextInt();         int gy = sc.nextInt();         int walkTime = sc.nextInt();         int taxTime = sc.nextInt();         int timeWalk = (Math.abs(gx) + Math.abs(gy)) * walkTime;         int timeTax = timeWalk;         for (int i = 0; i < taxNum; i++) {             timeTax = Math.min(timeTax, ((Math.abs(taxX[i]) + Math.abs(taxY[i])) * walkTime                     + (Math.abs(gx - taxX[i]) + Math.abs(gx - taxX[i])) * taxTime));         }                  System.out.println(timeTax);     }
}

发表于 2017-09-17 20:21:18 回复(0)
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args)
        {
        Scanner sc=newScanner(System.in);
        intn=sc.nextInt();
        intx[]=newint[n];
        for(inti=0;i<n;i++){
            x[i]=sc.nextInt();
        }
        inty[]=newint[n];
        for(inti=0;i<n;i++){
            y[i]=sc.nextInt();
        }
        intgx=sc.nextInt();
        intgy=sc.nextInt();
        intwt=sc.nextInt();
        inttt=sc.nextInt();
         
        inttime=0;
        if(wt<=tt){
             time=(Math.abs(gx)+Math.abs(gy))*wt;
        System.out.println(time);
        }
        else{
            time=(Math.abs(x[0])+Math.abs(y[0]))*wt+(Math.abs(x[0]-gx)+Math.abs(y[0]-gy))*tt;
           for(inti=0;i<n;i++){
            time=Math.min(time,(Math.abs(x[i])+Math.abs(y[i]))*wt+(Math.abs(x[i]-gx)+Math.abs(y[i]-gy))*tt);
             
        }
        time=Math.min(time,(Math.abs(gx)+Math.abs(gy))*wt);
        System.out.println(time);
        }
         
         
    }
}
发表于 2017-08-14 14:01:56 回复(0)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
int main(){
    int taxi_num = 0;
    cin >> taxi_num;
    vector<int> tx;
    vector<int> ty;
    int i = 0,j = 0;
    for(int i = 0;i < taxi_num;i++){
        int x;
        cin >> x;
        tx.push_back(x);
    }
   for(int i = 0;i < taxi_num;i++){
        int y;
        cin >> y;
        ty.push_back(y);
    }
    int fx,fy;
    cin>>fx>>fy;
    int wt,tt;
    cin>>wt>>tt;
     
    int min_time = 0x7FFFFFFF;
    int sum = 0,nx,ny,tl,time2;
    for(int i = 0; i < taxi_num;i++){
        sum = abs(tx[i])+ abs(ty[i]);
        nx = tx[i];
        ny = ty[i];
        tl = abs(fx-nx) + abs(fy -ny);
        time2 = sum * wt + tl * tt;      //走到最近的出租车点,坐车
        if(min_time > time2){
            min_time = time2;
        }
    }
         
    int time1 = wt * (abs(fx) + abs(fy));//只是步行
     
    if(min_time < time1)
        cout << min_time << endl;
    else
        cout << time1 << endl;
    return 0;
}

发表于 2017-08-12 12:09:40 回复(0)