java - java中的汽车加油问题。任何人都可以找出while循环条件中的任何错误吗？

Question

import java.util.*;
import java.io.*;

public class CarFueling {
 static int compute_refills(int dist,int tank,int stops[],int n){
    
        int current_refills=0;
        int num_refills=0;
        int last_refill=0;
        while(current_refills<=n) {
             last_refill = current_refills;
            while ((current_refills <= n) && (stops[current_refills + 1] - stops[last_refill]) <= tank) {
                current_refills = current_refills + 1;
            }

            if (current_refills == last_refill)
                return -1;
            if (current_refills <= n)
                num_refills = num_refills + 1;


        }
        return num_refills;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int dist = scanner.nextInt();
        int tank = scanner.nextInt();
       int n = scanner.nextInt();
        int stops[] = new int[n*n*n];// to solve array index out of bound exception increase the size of the array
        for (int i = 0; i < n; i++) {
            stops[i] = scanner.nextInt();
        }

       System.out.println(compute_refills(dist,tank,stops,n));

    }
}

我认为我的 while 循环条件存在一些问题。
输入：
950 400
4
200 375 550 750
我的输出：
1
正确输出：
2

标签： javaarraysalgorithmwhile-loopgreedy

Answer 1

如果你看

(current_refills <= n) && (stops[current_refills + 1] ... )

部分，两件事：

• current_refills <= n两者都为真n-1（n 元素数组的最后一个元素，因为第一个元素的索引为 0）和n（已经在数组之外）
• 然后stops[current_refills + 1]访问“稍后”的元素，对于这两种情况，该元素比最大值高 1 或 2 个元素

但实际上这可以工作，只是你可以添加 0 作为行程的开始和dist结束：

int n = scanner.nextInt();
int stops[] = new int[n+2];
stops[0] = 0; // well, it is 0 already
stops[n+1] = dist;
for (int i = 1; i <= n; i++) {
    stops[i] = scanner.nextInt();
}

然后compute_refills()可能会正常工作（尽管我没有检查过）。