Я решал вопрос о емкости NeetCode для отправки пакетов в течение D дней.
Решение включает в себя выполнение двоичного поиска по всем возможным значениям весов (то есть от максимального веса в массиве до
до суммы всех весов в массиве), для каждого такого значения веса я запускаю функцию valid(), чтобы выяснить, использую ли этот минимальный вес, могу ли я отправить все веса за d дней, но я допустил ошибку в его реализации.
Я все равно отправил свой ответ и обнаружил, что мой ответ всегда был на один больше, чем ожидаемый ответ, поэтому я решил вернуть на один меньше, чем ответ, который выдал мой код, и на удивление он прошел все тестовые случаи.
Пытаясь выяснить, почему возврат на один меньше работал, я понял, что в функции valid() была ошибка. Если у нас есть вес, равный нашему предполагаемому весу (из двоичного поиска), он будет каждый раз выполнять код else, который не увеличивает итератор i, и будет продолжать увеличивать d до тех пор, пока не будет выполнено условие d>days и оно не вернет false, но каким-то образом все это работает отлично.
Плюс, сколько бы я ни старался, я не могу найти ни одного тестового случая, в котором этот код дает сбой, я также понятия не имею, почему этот код вообще работает. Функция valid() — единственная ошибочная часть, из-за которой w всегда оказывается на единицу больше, чем ожидалось.
Я пробовал писать каждый шаг и отслеживать каждую переменную, но все это работает, но я не мог объяснить, почему.
class Solution {
private:
bool valid(const vector& weights, const int& n, const int& days, const int& w){
int d = 1, i = 0, mx = w;
while(idays) return false;
}
return true;
}
public:
int shipWithinDays(const vector& weights, const int& days) {
int n = weights.size();
int mn = weights[0];
int mx = weights[0];
for(int i = 0; i mn) mn = weights;
}
int w = mx;
while(mn >1);
if(valid(weights,n,days,m)){
w = m;
mx = --m;
}else{
mn = ++m;
}
}
return w-1;
}
};
Подробнее: https://stackoverflow.com/questions/799 ... n-neetcode
