0

Знаю, что уже есть, не хватает репутации комментировать и отвечать.

Всего в одном месяце n дней. Вы знаете, что в этом месяце будет проходить m фэшн-эвентов. i-й фэшн-эвент будет проходить со дня li по день ri включительно. Во все дни i-го фэшн-эвента стоимость вашего наряда должна быть хотя бы xi. Конечно же нельзя носить одно и то же, поэтому каждый день, когда проходит хотя бы один фэшн-эвент, вы покупаете новый наряд. Заметьте, что в один день может быть несколько эвентов, но для них надо купить только один наряд. Сообщите минимальное суммарное количество денег, которое потребуется, чтобы удовлетворить условия всех фэшн-эвентов.

Формат ввода В первой строке вводится два числа n и m (1 ≤ n ≤ 109, 1 ≤ m ≤ 105). Следующие m строк описывают фэшн-эвенты. В i-й строке записаны 3 числа li, ri и xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 109) — даты фэшн-эвента и минимальная стоимость наряда.

Формат вывода Выведите минимальное суммарное количество денег, необходимое для удовлетворения условий всех фэшн-эвентов.

Пример 1

Ввод    Вывод  
10 3       63  
1 5 5  
6 10 6  
3 7 7  

Пример 2

Ввод    Вывод  
3 4        9  
1 2 2  
2 3 3  
2 2 1  
2 2 4  

Есть решение, похожее на https://ru.stackoverflow.com/questions/1396284/Задача-модник-на-c/1397005, оно работает, но долго.(Человек забыл инициализировать вектор, ответьте ему, пожалуйста, если не сложно). И собственно вопрос: как сделать код быстрее?

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    long long n, m, r, l, x;
    cin >> n >> m;
    vector<long long> mass(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        cin >> r >> l >> x;
        for (long long j = r; j <= l; ++j) {
            mass[j] = max(mass[j], x);
        }
    }
    long long ans = 0;
    for (int i = 1; i < n + 1; ++i) {
        ans += mass[i];
    }
    cout << ans;
}
3
  • Задача на дерево отрезков, как я понимаю...
    – Harry
    10 апр 2022 в 16:51
  • Это задача на неявное до с операцией минимума и присвоения на отрезке, образно если у вас 1e9 дней то вы не можете просто хранить массив. Но как я помню есть решение проще с помощью сканлайна, сортируем события с ивенатами и просто проходимся по ним запоминаю минимальный наряд в этой время, как только вестиваль начинается, мы добавляем в очередь минимальную стоимость наряда, а как заканчивается мы ее извелкаем
    – Neuro
    11 апр 2022 в 15:32
  • я добавлю ответ с кодом
    – Neuro
    11 апр 2022 в 15:32

1 ответ 1

1

Задачу можно решить несколькими способами. Скан лайн(сканирующая прямая) один из наиболее оптимальных(ДО не будет работать из-за большого кол-во дней в месяце). Для того чтобы решить эту задачу с помощью скан лайна нужно обработать каждое событие(начало и конец ивента) во временном порядке. Все суммы мы храним в сете, чтобы оперативно добавлять туда элемент и извлекать. Обрабатывая день к суме мы прибавляем длительность между событиями и минимальную цену этого события.

int n, m;
cin >> n >> m;
deque <pair<int,int>> dates;
for (size_t i = 0; i < m; i++){
    int l, r, x;
    cin >> l >> r >> x;
    dates.push_back({l,x});
    dates.push_back({r+1,-x});
}
sort(dates.begin(), dates.end());
multiset <int, greater<int>> cost;
long long sum = 0;
cost.insert(0);
int pday = dates.front().first;
while (dates.size()){
    pair<int,int> s = dates.front();
    sum += (s.first-pday)*(*cost.begin());
    if(s.second < 0){
        cost.erase(cost.find(-s.second));
    } else {
        cost.insert(s.second);
    }
    pday = s.first;
    dates.pop_front();
}
cout << sum << endl;
2
  • Выглядит как правда, но тест 3 не проходит:( Возможно, суть в том, что если два события пересеклись, то надо брать цену костюма от более дорогого события.
    – Logashka
    14 апр 2022 в 4:35
  • У вас переполнение тут: (s.first-pday)*(*cost.begin()). 26 мая 2022 в 17:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.