加油站（贪心）

题目

小伟要开车去一个与他家距离为 L(1 <= L <= 1000000) 个单位的地方旅行， 他从家里出发时车上有 P(1 <= P <= 1000000) 单位的汽油， 汽车每行驶 1 单位的路程要消耗 1 单位的汽油。 如果汽车在中途汽油耗尽就无法继续前行， 因而无法到达目的地。 在途中一共有 N(1 <= N <= 10000) 个加油站， 第 i 个加油站在距离终点 Ai(1 <= Ai <= L) 单位的地方， 最多给汽车加 Bi(1 <= Bi <= 100) 单位的汽油。 假设汽车的油箱容量无限大， 请问小伟能不能顺利到达目的地呢？如果可以，输出最少加多少次油， 不可以则输出 -1。

提示

车在开往终点的途中, 只有在加油站才能加油. 但是, 可以认为在到达加油站 i 时, 就获得了一次在之后的任何时候都可以加 Bi 单位的汽油的权利, 在解决这个问题上也是一样, 而在之后需要加油时, 就认为是在之前经过的加油站加的油就可以了, 因为希望在到达终点时加油的次数尽可能的少, 所以当燃料为 0 了之后在进行加油就行, 当燃料为 0 时, 选用加油量最大的加油站. 为了提高效率, 可以用优先队列来存储有权利加的油的油量.

代码

package com.company;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class OJ53 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            int W = sc.nextInt(), width = W;

            int startX = 0, startY = 0, count = 1;
            int numTriangle = width / 3 + (width % 3 == 0 ? 0 : 1);
            int[][] buff = new int[width][width];

            for (int i = 0; i < numTriangle; i++) {
                for (int j = 0; j < width; j++) {
                    buff[startX][startY + j] = count;
                    count += 1;
                }

                for (int j = 0; j < width - 1; j++) {
                    buff[startX + j + 1][startY + width - 2 - j] = count;
                    count += 1;
                }

                for (int j = 0; j < width - 2; j++) {
                    buff[startX + width - 2 - j][startY] = count;
                    count += 1;
                }

                startX += 1;
                startY += 1;
                width -= 3;
            }

            for (int i = 0; i < W; i++) {
                System.out.println(Arrays.stream(buff[i]).filter(x -> (x != 0)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
            }
        }
    }
}