Давайте выберем нежелательный алгоритм, который, как мы знаем, неверен, чтобы понять, почему он неправильный ...
нотации ...
Текущая точка: (галлоны газа в текущей точке, галлоны, необходимые для создания следующей точки) -> Оставшийся газ (галлоны)
В немного более математической форме:
P [i]: (g (P [i]), d (P [i + 1])) -> сумма (g (P [i]) - d (P [i + 1]))) от i = 1 до текущей точки-1
(А теперь плохой алгоритм ...)
P1: (2,2) -> 0 (at P2)
P2: (5,3) -> 2 (at P3)
P3: (2,4) -> 0 (at P4)
P4: (2,5) -> -3 (ran out of gas 3 miles short of P5)
Чтобы добраться до P5, нам нужно иметь три дополнительных галлона газа к тому времени, когда мы дойдем до P3, и чтобы иметь 3 дополнительных галлона на P3, нам нужно иметь 3 дополнительных галлона на P1:
??? -> +3 (at P1)
P1: (2,2) -> 0+3 = 3 (at P2)
P2: (5,3) -> 2+3 = 5 (at P3)
P3: (2,4) -> 0+3 = 3 (at P4)
P4: (2,5) -> -3 +3 = 0 (made it to P5)
Поэтому хитрость заключается в том, чтобы найти самые худшие участки - там, где вам не дают достаточно газа, чтобы пройти их. Мы знаем , мы не можем начать с P4, P3, P2 или P1. Мы должны начать где-то раньше и накопить достаточно газа, чтобы пройти через плохой участок.
Без сомнения, в круге будет много плохих участков, что несколько усложнит, но на самом деле довольно легко понять, как это сделать.
возможно , что следующие несколько точек после самого худшего отрезка в круге могут быть пройдены после отрезка, но только если они не изменят ваши запасы газа. (например, точка после наихудшего растяжения дает вам 2 галлона газа и заставляет вас пройти 2 галлона расстояния до следующей точки.)
В некоторых случаях, однако, худший раздел ДОЛЖЕН быть последним. Это потому, что перед тем, как вы начнете работать с этим разделом, вам нужно накопить как можно больше газа, и следующий пункт после худшего отрезка может дать вам последний кусок газа, который вам нужен, а это значит, что вам нужно пройти его до того, как брать на худшем отрезке. Хотя может существовать несколько решений, простой факт заключается в том, что обход самого худшего раздела - это ВСЕГДА решение. Вот некоторый код:
class point_ {
int gasGiven_;
int distanceToNextPoint_;
public:
int gasGiven() {return gasGiven_;}
int distanceToNextPoint {return distanceToNextPoint_;}
}
class Circle_ {
public:
numberOfPoints;
point_ *P;
}
В основном ():
int indexWorstSection=0;
int numberPointsWorstSection=0;
int worstSum=0;
int currentSum=0;
int i=0;
int startingPoint =0;
// construct the circle, set *P to malloc of numberOfPoints point_'s, fill in all data
while (i<(Circle.numberOfPoints-1) || currentSum<0)
{
currentSum += Circle.P[i].gasGiven() - Circle.P[i].distanceToNextPoint();
if (currentSum < worstSum) { worstSum = currentSum; indexWorstSection=i-numberPointsWorstSection; startingPoint=i;}
if (currentSum>0) { currentSum=0; }
else { numberPointsWorstSection++; }
if (i==(Circle.numberOfPoints-1)) { i=0; }
else { i++; }
}
if (indexWorstSection<0) indexWorstSection=Circle.numberOfPoints+indexWorstSection;
Причина, по которой вы не можете сделать это циклом for, состоит в том, что наихудший раздел может быть, например, от i = (Circle.numberOfPoints -2) до i = 3. Если значение currentSum меньше нуля, оно должно продолжить в начале массива.
Не пробовал код и не занимался серьезным программированием почти десятилетие. Извините, если есть ошибки. Вам, несомненно, придется немного почистить это.