alexbuki
@alexbuki
программист js

Как разобраться в решении задачи? Что означает данный цикл решении к задаче чемпионата по ЯП?

Заранее прошу прощения за копипаст....
Разбираю задачу с прошлого чемпионата по яндекс программированию.
Не могу понять что делает в решении данный цикл:
while (j < days.length && days[j] < days[idx] + tickets[i].duration) {
                j++;
   }


Ссылка на оригинал задачи:
https://habr.com/en/company/yandex/blog/460139/

Текст задачи:
F. Поездки на метро

Условие

Есть девопс Петя. На работе ему нужно дежурить в определенные дни в течение последующих 100 дней. На работу Петя добирается на метро. В метро ввели билеты-абонементы, действующие определенное количество дней со дня первой поездки по ним. Чем больше длительность срока действия билета, тем меньше стоимость в пересчете на день. Нужно помочь Пете сэкономить деньги и рассчитать, какие билеты нужно ему купить на три месяца вперед, учитывая график его дежурств, таким образом, чтобы их суммарная стоимость была минимально возможной. А еще Петя не любит носить много билетов с собой, и если есть несколько вариантов билетов с одинаковой минимальной стоимостью, то Пете нужен такой, в котором меньше билетов. Если и таких вариантов окажется несколько (с одинаковой минимальной стоимостью и количеством билетов) — то Пете подойдет любой из них.

Вам необходимо написать функцию getCheapestTickets(days, tickets), принимающую на вход график дежурств Пети (days) и возможные варианты билетов-абонементов (tickets), а на выходе дающую список билетов (в виде индексов из входного массива вариантов билетов), которые нужно купить Пете.

График дежурств Пети задан в виде отсортированного массива чисел (от 1 до 100 включительно), каждое из которых обозначает порядковый номер дня дежурства:

[2, 5, 10, 45]  // Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно текущей даты.

Каждый билет-абонемент описывается следующим интерфейсом:
interface Ticket {
    duration: number; // количество дней, в течение которых билет действует со дня первой поездки по нему, включая этот день (от 1 до 100 включительно)
    cost: number; // стоимость билета (от 1 до 100 включительно)
}

Количество вариантов билетов не более 10, и гарантируется, что все билеты имеют разную стоимость, причем чем большее число дней действует билет, тем ниже его стоимость в пересчете на один день.
const days = [1, 2, 4, 6, 7, 8, 9, 10, 20];
const tickets = [
    { cost: 3, duration: 1 },
    { cost: 10, duration: 7 },
    { cost: 20, duration: 30 }
];

В первый и второй дни Пете нужно купить однодневные билеты, в четвертый день семидневный, на двадцатый день еще раз однодневный.

Суммарная стоимость таких билетов будет минимально возможной: 19.

Решение:
Одно из возможных решений — методом динамического программирования, а именно:

1. Берем первый день дежурства Пети.
2. Чтобы найти лучшее решение для этого дня, рассчитаем возможные варианты по каждому из билетов. Каждый такой вариант складывается из стоимости билета и стоимости лучшего решения в день дежурства, следующего за днем окончания действия этого билета. Второе слагаемое рассчитываем аналогично, таким образом получая рекурсию.
3. Дополнительно учитываем количество билетов, если таких вариантов оказывается несколько.
4. Особое внимание следует уделить кэшированию решений в промежуточных днях.

function (days, tickets) {
    if (days.length === 0 || tickets.length === 0) {
        return [];
    }

    tickets = tickets
        .map((ticket, idx) => ({
            ...ticket,
            idx
        }))
        .sort((a, b) => a.duration - b.duration);

    const daysSolutions = new Map();

    function getDaySolution(idx) {
        if (daysSolutions.has(idx)) {
            return daysSolutions.get(idx);
        }

        const solution = {
            totalCost: Number.POSITIVE_INFINITY,
            totalTickets: Number.POSITIVE_INFINITY,
            ticketToBuy: null,
            next: null
        };

        for (let i = 0, j = idx; i < tickets.length && j < days.length; i++) {
            while (j < days.length && days[j] < days[idx] + tickets[i].duration) {
                j++;
            }

            const nextDaySolution = j < days.length ? getDaySolution(j) : null;
            let totalCost = tickets[i].cost;
            let totalTickets = 1;

            if (nextDaySolution) {
                totalCost += nextDaySolution.totalCost;
                totalTickets += nextDaySolution.totalTickets;
            }

            if (
                totalCost < solution.totalCost ||
                (totalCost === solution.totalCost && totalTickets < solution.totalTickets)
            ) {
                solution.totalCost = totalCost;
                solution.totalTickets = totalTickets;
                solution.ticketToBuy = tickets[i].idx;
                solution.next = nextDaySolution;
            }
        }

        daysSolutions.set(idx, solution);

        return solution;
    }

    let solution = getDaySolution(0);
    const res = [];

    while (solution) {
        res.push(solution.ticketToBuy);
        solution = solution.next;
    }

    return res;
};
  • Вопрос задан
  • 104 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы