Алгоритмическая задача

Question

Вот сама задача:

Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.

Моя идея по решению этой задачи: будем ставить машинки на пол, пока все место на полу не будет занято. Когда это произойет, тогда мы уберём такую машинку, которую мы уже ставили, но такой, которой нет в дальнейшей последовательности, и вместо неё мы возьмем ту, которая нам нужна(стоит следующей в последовательности). Если нет такой машинки, то мы возьмем ту, которая дальше всех стоит в последовательности, относительно того момента, где мы сейчас находимся, и уберем её.

Реализовать я думал так: положим последовательность в массив, и посчитаем расстояние от 1-го члена последовательности до такой машинки, и если эта машинка уже на полу, положим это число в кучу.

Мне кажется я не совсем правильно реализовываю. Помогите как реализовать мой алгоритм (если он, конечно, верный)

Answer 1

Вот пример реализации. Идея кстати, у тебя правильная:

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    int n, k, p,x, ans=0;
    cin >> n >> k >> p;
    vector<vector<int>> a(n);
    vector<int> b;
    for (int i = 0;i < p;i++) {
        cin >> x;
        a[x - 1].push_back(i);
        b.push_back(x-1);
    }
    for (int i = 0;i < n;i++) {
        a[i].push_back(1e9);
        reverse(a[i].begin(), a[i].end());
    }
    
    set<pair<int, int>> s;
    for (int i = 0;i < p;i++) {
        auto elem = s.find({ a[b[i]].back(), b[i] });

        if (elem != s.end()) {
            s.erase(elem);
        }
        else {
            ans++;
            if (int(s.size()) >= k){
                s.erase(prev(s.end()));
            }
        }
        a[b[i]].pop_back();
        s.insert({ a[b[i]].back(), b[i] });
    }
    cout << ans;
}

БЛОГ НА HUSL

Алгоритмическая задача

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