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