Задача нахождения оптимального пути между этажами

Question

Есть следующая задача: У Кати насыщенный день на работе. Ей надо передать n разных договоров коллегам. Все встре- чи происходят на разных этажах, а между этажами можно перемещаться только по лестничным пролетам — считается, что это улучшает физическую форму сотрудников. Прохождение каждого пролета занимает ровно 11 минуту.

Сейчас Катя на парковочном этаже, планирует свой маршрут. Коллег можно посетить в любом порядке, но один из них покинет офис через tt минут. С парковочного этажа лестницы нет — только лифт, на котором можно подняться на любой этаж.

В итоге план Кати следующий:

Подняться на лифте на произвольный этаж. Считается, что лифт поднимается на любой этаж за 00 минут. Передать всем коллегам договоры, перемещаясь между этажами по лестнице. Считается, что договоры на этаже передаются мгновенно. В первые tt минут передать договор тому коллеге, который планирует уйти. Пройти минимальное количество лестничных пролетов. Помогите Кате выполнить все пункты ее плана.

Формат входных данных: В первой строке вводятся целые положительные числа nn и tt (2\leq n,t \leq 100)(2≤n,t≤100) — количество сотрудников и время, когда один из сотрудников покинет офис (в минутах). В следующей строке n чисел — номера этажей, на которых находятся сотрудники. Все числа различны и по абсолютной величине не превосходят 100. Номера этажей даны в порядке возрастания. В следующей строке записан номер сотрудника, который уйдет через t минут.

Формат выходных данных: Выведите одно число — минимально возможное число лестничных пролетов, которое понадобится пройти Кате.

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  int t;
  cin >> n >> t;
  vector<int> floors;
  int buf;
  for (int i = 0; i < n; i++) {
    cin >> buf;
    floors.push_back(buf);
  }
  int leave;
  cin >> leave;
  int leaveFloor = floors[leave - 1];
  int maxFloor = floors[n - 1];
  int minFloor = floors[0];
  int result = 0;
  if (leaveFloor > t && (maxFloor - leaveFloor) > t) {
    int timeAfterStartFloor = 0;
    if (maxFloor - leaveFloor >= leaveFloor - minFloor) {
      timeAfterStartFloor = leaveFloor - minFloor;
      result += timeAfterStartFloor;
    } else {
      timeAfterStartFloor = maxFloor - leaveFloor;
      result += timeAfterStartFloor;
    }
  }
  result += floors[n - 1] - floors[0];
  cout << result << endl;
  return 0;
}

Вопрос: Что не так с решением? не проходит тесты(

Answer 1

Пример:

n = 3;
t = 1;
этажи 10, 11, 13;
уходящий сотрудник 2.

Ваша программа решит что надо ехать на 11 этаж, спуститься на 10, подняться на 13 - всего четыре этажа.

Правильное решение - ехать на 10, подняться на 13 - три этажа.

Ошибка в условии leaveFloor > t - нет смысла сравнивать абсолютные номера этажей с чем бы то ни было. Значение имеют только разницы между номерами этажей: leaveFloor - minFloor > t.

Answer 2

Если тебе нужен код чуть проще, чтобы разобраться, то прикреплю его ниже:

#include <iostream>

using namespace std;

int main() {
    int n, t, man;
    cin >> n >> t;
    int nums[n];
    for (int i = 0; i < n; ++i)
        cin >> nums[i];
    cin >> man;
    if (man == 1 || man == n || min(nums[man - 1] - nums[0], nums[n - 1] - nums[man - 1]) <= t)
        cout << nums[n - 1] - nums[0];
    else
        cout << min(nums[man - 1] - nums[0], nums[n - 1] - nums[man - 1]) + nums[n - 1] - nums[0];
}

Объяснение:

В случаях, когда данный нам сотрудник располагается на первой или последней позициях, или расстояние между первой позицией и позицией сотрудника или расстояние между последней позицией и позицией сотрудника не превосходит t, то мы можем пройти все этажи разом (либо сверху вниз, либо снизу вверх);
Если же ни одно из этих условий не выполнено, то логично будет сразу же подняться на этаж данного нам сотрудника и дойти до того этажа (первого или последнего), который ближе к этажу этого сотрудника, так как мы будем потом проходить абсолютно все этажи, чтобы дойти до другого конца этажа (первого или последнего).

Answer 3

Решение для Java 17.05:

import java.util.ArrayList;
import java.util.Scanner;
import java.lang.Math;
public class Katya_floor1 {


    int floor_travel(){
        Scanner scn = new Scanner(System.in);
        System.out.println("Input n t: ");


        int n = scn.nextInt();
        int t = scn.nextInt();
        System.out.println("n: " + n);
        System.out.println("t: " + t);

        ArrayList<Integer> floors = new ArrayList<Integer>();
        for(int i =0; i<n; i++)
        {
            floors.add(scn.nextInt());
        }
        System.out.println("floors: " + floors);
        int person = scn.nextInt();
        System.out.println("person: " + person);
        Integer neibohour = Math.min((floors.get(person - 1) - floors.get(0)), 
                                     (floors.get(n - 1) - floors.get(person - 1))) ;
        Integer result = 0;
        if (person == 1 || person == n || neibohour<=t)
            result = (floors.get(n - 1) - floors.get(0));
        else
            result = Math.min(
                floors.get(person - 1) - floors.get(0),
                floors.get(n - 1) - floors.get(person - 1))
                    + floors.get(n - 1) - floors.get(0);

        System.out.println("Result: " + result);
        return result;
    }
}

БЛОГ НА HUSL

Задача нахождения оптимального пути между этажами

Ответы (3 шт):