読者です 読者をやめる 読者になる 読者になる

マトリョーシカ的日常

ワクワクばらまく明日のブログ。

点在するタクシータクシー(SRM400 div2 level1)

topcoder

タクシーを使っていこう

http://instagr.am/p/W0d6ZlhBPx/
topcoder

TopCoder Statistics - Problem Statement

正答率85%です。そんなに難しいものではありません。
問題:無限に広がる座標の町の中心に男は立っていた。突然上司から電話がかかり、今すぐ会社へ来るように言われる。ポイント(gX,gY)地点にその会社はある。歩いても行くことができるが、なるべく速く向いたい。この町にはタクシーの停留所が点在しており、そのポイントはtXs,tYsの配列に格納されている。
 一区画歩く時間、タクシーで移動する時間がそれぞれ与えられている。最短時間を求めよ。

 コード。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
 class GrabbingTaxi{
    public:
     int minTime(vector <int> tXs,vector <int> tYs, int gX,int gY,int wT,int tT){
         int minT,Time;
         minT=wT*(abs(gX)+abs(gY));
         cout << "mT=" << minT<<endl;
         for(int i=0;i<tXs.size();i++){
             Time=wT*(abs(tXs[i])+abs(tYs[i]))+tT*(abs(gX-tXs[i])+abs(gY-tYs[i]));
             cout << "Time="<< Time <<endl;
             minT=min(minT,Time);
         }
         cout << "minimumTime="<< minT <<endl;

         return minT;
     }
};

int main(){
    GrabbingTaxi ob1;
    int a[]={82, -60, 57, 98, 30, -67, 84, -42, -100, 62};
    int b[]={-7, 90, 53, -56, -15, -87, 22, -3, -61, -30};
    vector <int> tx(a,a+10);
    vector <int> ty(b,b+10);
    int gx=21,gy=15,wt=53,tt=2;
    ob1.minTime(tx,ty,gx,gy,wt,tt);
    return 0;
}
  • はじめに徒歩のみで向った場合の時間を計算。
  • つぎにタクシーを使った場合の時間を計算。停留所ごとに繰り返し。

おわり。