public static void main(String[] args) {
gas(new int[] { 1, 3, 8 });
}
public static void gas(int[] a) {
if (a == null || a.length == 0) {
return;
}
if (a.length == 1) {
System.out.printf("最小需要進行調度的油量：%d\n", 0);
return;
}
int total = sum(a); // 總油量
if (total % a.length != 0) {
System.out.println("Impossible");
return;
}
int average = total / a.length; // 最終每個站平均油量
if (a.length == 2) {
System.out.printf("最小需要進行調度的油量：%d\n", Math.abs(a[0] - average));
return;
}
int move = 0;
for (int i = 0; i < a.length; i++) {
int pre = pre(i, a);
int next = next(i, a);
while (pre != i && next != i && a[i] > average) {
if (a[pre] < average) {
int gasAmount = Math.min(a[i] - average, average - a[pre]);
a[i] -= gasAmount;
a[pre] += gasAmount;
move += distance(pre, i, a) * gasAmount;
}
if (next == pre) {
break;
}
if (a[i] > average && a[next] < average) {
int gasAmount = Math.min(a[i] - average, average - a[next]);
a[i] -= gasAmount;
a[next] += gasAmount;
move += distance(i, next, a) * gasAmount;
}
pre = pre(pre, a);
if (next != pre) {
next = next(next, a);
}
}
}
System.out.printf("最小需要進行調度的油量：%d\n", move);
}
private static int distance(int i, int j, int[] a) {
if (i == j) {
return 0;
}
if (i < j) {
return j - i;
} else {
return a.length - i + j;
}
}
/**
* 求 i 位置的前壹個位置。
*
* @param i
* @param a
* @return
*/
private static int pre(int i, int[] a) {
return i > 0 ? i - 1 : a.length - 1;
}
/**
* 求 i 位置的後壹個位置。
*
* @param i
* @param a
* @return
*/
private static int next(int i, int[] a) {
return (i + 1) % a.length;
}
/**
* 求總油量。
*
* @param a
* @return
*/
private static int sum(int[] a) {
int sum = 0;
for (int i : a) {
sum += i;
}
return sum;
}