Путешествие между двумя городами с кабинами от

Question

Вы хотите добраться из города A до B, находящегося в милях на миллион, с помощью некоторого количества кабин. Где-то между городами (или в одном из них) находится кабина (каждая кабина начинает свое путешествие с базы). Каждая кабина имеет топливо в течение нескольких миль (ни одна из кабин не должна возвращаться на базу). Определите, возможно ли ваше путешествие с A до B.

ВХОД:

Целые м, д, п (1 < = д < = т < = 10^8, 1 < = п < = 500000), что означает (в этом порядке): расстояние от А до B, расстояние от А до базы кабины, номер кабины. После этого n целых чисел означает, что i-я кабина имеет топливо для x_i-го миль пути.

ВЫВОД:

Одно целое число: минимальное количество такси вы будете использовать, чтобы получить от А до Б или 0, если это невозможно.

Я попытался справиться с этим с первым штрихом моего разума и (не удивительно), что это не было хорошей идеей. А именно, что я сделал:

sort(ALL(cabs)); 
reverse(ALL(cabs)); 

for(int i = 0; i < n; ++i) 
{ 
    toPosition = position <= d ? d-position : position - d; 

    if(cabs[0] <= toPosition) {printf("0"); return 0;} 

    position += (cabs[0]-toPosition); 
    cabs.erase(cabs.begin()); 
    ++solution; 

    if(position >= m) {printf("%lld", solution); return 0;} 
} 

Теперь toPosition расстояние от основания до текущего position мы находимся Тогда мы берем такси с полным бензобаком от основания (если нет ни одного. чтобы он мог приблизить нас к городу B, нет решения). Мы соответствующим образом меняем наш position (до максимальной пропускной способности кабины), снимите кабину и просто сделайте это, пока мы не в городе B.

Теперь я знаю, что решение неверно. Я даже нашел некоторые тесты, где он терпит неудачу. Однако я не могу понять, почему это происходит. Так, например, для испытания

14 4 2 
10 8 

Он выводит 0 в то время как он должен вывести 2. Я знаю, что это потому, что хочет идти 10-> 8 в то время как правильный порядок здесь 8 -> 10. Теперь вот где проблема возникает:

Почему этот вопрос имеет значение здесь в этой проблеме? Если нам все равно нужно покрыть все расстояние от А до В, и пока мы не войдем в базовое местоположение или после него, нам нужно вернуться с каждой кабиной, почему бы не использовать те, которые быстрее выполняли бы миссию по возврату?

Answer 1

Представьте, что у вас было 3 кабины, где только 1 имеет достаточное количество топлива, чтобы добраться до А, и он может получить вас на расстоянии 1 мили от базы; у вас достаточно топлива, чтобы доставить вас от базы до B; и у последнего достаточно топлива для 2-мильной поездки. Ясно, что вам нужно использовать «самую маленькую» секунду; если бы вы использовали другой, вы бы просто стеснялись B, с кабиной, которая не может связаться с вами, а тем более закончить работу.

Итак, да, порядок имеет значение.

Answer 2

• д: расстояние в кабину базовой
• м: расстояние от А до Б
• INT [] cabMilliage: мили, что каждая кабина может сделать

---

Я полагал, один оптимизации стратегию, которую вы могли бы использовать: Начните строить свой путь «назад», от последнего кабины до первого. Чтобы покрыть расстояние от основания кабины до B, вы будете использовать только одну кабину, не можете использовать более одного, поэтому начните, выбрав этот. distBaseToB = m - d; Выберите минимальный cabMilliage [я]> = distBaseToB

вычислить точку, в которой эта кабина забрать вас pickUpPoint [0] = D - (cabMilliage [я] - distBaseToB)/2 сейчас, по-прежнему с петлей, выбирая минимальный cabMilliage [], который может забрать вас раньше на пути и принести вам pickUpPoint [0] до тех пор, пока вы не достигнете A (или не выйдете из кабин, которые могут забрать вас в этом месте дороги, потому что они не есть достаточно газа.)