題目描述

一輛汽車(chē)在一條筆直的道路上行駛运翼，一開(kāi)始有original單位的汽油屯换。這條筆直的道路上有n個(gè)加油站薯嗤，第i個(gè)加油站距離汽車(chē)出發(fā)位置的距離為distance[i]單位距離栏尚，可以給汽車(chē)加apply[i]單位汽油归苍。汽車(chē)每行駛1單位距離會(huì)消耗1單位的汽油宠默，假設(shè)汽車(chē)的油箱可以裝無(wú)限多的汽油麸恍。目的地距離汽車(chē)出發(fā)位置的距離為target，請(qǐng)問(wèn)汽車(chē)能否到達(dá)目的地搀矫，如果可以返回最少的加油次數(shù)抹沪，否則返回-1。

思路點(diǎn)撥

考慮貪心瓤球，每次都用能到達(dá)并且能加最多油的加油站加油融欧。

考點(diǎn)分析

本題考察了用優(yōu)先隊(duì)列來(lái)貪心的思想。對(duì)于汽車(chē)能到達(dá)的加油站冰垄，顯然采用能提供油最多的加油站加油蹬癌，這樣才能保證到達(dá)目的地后加油次數(shù)最少，這個(gè)貪心的思想很有特色很值得借鑒虹茶。

參考程序

http://www.jiuzhang.com/solution/gas-station-ii/

/**
* 本參考程序來(lái)自九章算法逝薪，由 @華助教 提供。版權(quán)所有蝴罪，轉(zhuǎn)發(fā)請(qǐng)注明出處董济。
* - 九章算法致力于幫助更多中國(guó)人找到好的工作，教師團(tuán)隊(duì)均來(lái)自硅谷和國(guó)內(nèi)的一線(xiàn)大公司在職工程師要门。
* - 現(xiàn)有的面試培訓(xùn)課程包括：九章算法班虏肾，系統(tǒng)設(shè)計(jì)班廓啊，算法強(qiáng)化班，Java入門(mén)與基礎(chǔ)算法班封豪，Android 項(xiàng)目實(shí)戰(zhàn)班谴轮，
* - Big Data 項(xiàng)目實(shí)戰(zhàn)班，算法面試高頻題班, 動(dòng)態(tài)規(guī)劃專(zhuān)題班
* - 更多詳情請(qǐng)見(jiàn)官方網(wǎng)站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param target: The target distance
     * @param original: The original gas
     * @param distance: The distance array
     * @param apply: The apply array
     * @return: Return the minimum times
     */
    class Station {
        public int d;
        public int gas;
        public Station(int d, int gas) {
            this.d = d;
            this.gas = gas;
        }
    }

    public static Comparator<Station> gasComparator = new Comparator<Station>(){
        public int compare(Station a, Station b) {
            return b.gas - a.gas;
        }
    };
    public static Comparator<Station> dComparator = new Comparator<Station>(){
        public int compare(Station a, Station b) {
            return a.d - b.d;
        }
    };

    public int getTimes(int target, int original, int[] distance, int[] apply) {
        // Write your code here
        Queue<Station> q = new PriorityQueue<Station>(distance.length, gasComparator);
        Station[] s = new Station[distance.length];
        for(int i = 0; i < distance.length; i++) {
            s[i] = new Station(distance[i], apply[i]);
        }
        Arrays.sort(s, dComparator);
        int ans = 0;
        int i = 0;
        while(original < target && i < distance.length) {
            while(i < distance.length && original >= s[i].d) {
                q.offer(s[i]);
                i++;
            }
            Station now = q.poll();
            if(now == null) {
                break;
            }
            original += now.gas;
            ans++;
        }
        if(original >= target) {
            return ans;
        } else {
            return -1;
        }
    }
}