Помогите пожалуйста решить задание на с++.

Question

Помогите пожалуйста решить задание на с++.

Ирина Ученик (188), на голосовании 9 месяцев назад

На с++. Голодная капибара Артем — очень голодная капибара, но у него совершенно нет еды и ему придется съесть свой любимый газон. Газон Артема можно представить как n рядов, каждый из которых характеризуется красотой bi и аппетитность ti . Чтобы наесться, Артему нужно съесть ровно k рядов своего газона. Артем хочет наесться, но не хочет испортить внешний вид своего газона. Поэтому он хочет выбрать k рядов и съесть их таким образом, чтобы максимизировать суммарную красоту оставшихся рядов. В случае, если у него есть несколько способов выбрать k рядов газона, чтобы суммарная красота оставшихся рядов была максимальна, он выберет такие ряды, чтобы максимизировать суммарную аппетитность съеденных рядов. Помогите Артему выбрать k рядов газона требуемым образом.

Answer 1

Итак, задача состоит в том, чтобы найти k рядов, которые следует убрать, чтобы максимизировать оставшуюся общую красоту и в то же время максимизировать общую аппетитность удаленных рядов.

Решение данной задачи может быть найдено с помощью подхода, называемого "жадным алгоритмом". Сначала все ряды сортируются по красоте, а затем выбираются k рядов с наименьшей красотой. Если есть несколько рядов с одинаковой красотой, то выбираются те, у которых наибольшая аппетитность.

Вот код на C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct LawnRow {
int beauty, tastiness;
};

bool cmp(const LawnRow& a, const LawnRow& b) {
if (a.beauty == b.beauty)
return a.tastiness > b.tastiness;
return a.beauty < b.beauty;
}

int main() {
int n, k;
cin >> n >> k;

vector<LawnRow> lawn(n);
for (int i = 0; i < n; ++i) {
cin >> lawn[i].beauty >> lawn[i].tastiness;
}

// Сортируем ряды газона
sort(lawn.begin(), lawn.end(), cmp);

// Выбираем первые k рядов
for (int i = 0; i < k; ++i) {
cout << "Выбран ряд " << i+1 << " с красотой " << lawn[i].beauty << " и вкусом " << lawn[i].tastiness << endl;
}

return 0;
}

В этом коде используется структура `LawnRow` для представления рядов газона, функция `cmp` для определения порядка сортировки, и входные данные считываются в вектор структур `lawn`. После сортировки выводятся данные о первых `k` рядах, которые следует съесть.