Professional Professional
Мудрец
(14369)
3 месяца назад
Итак, задача состоит в том, чтобы найти 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` рядах, которые следует съесть.