Формулировка задачи
Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.
Тесты
| [latex]V[/latex] | [latex]n[/latex] | [latex]Menu[/latex] | [latex]Recipe[/latex] | Комментарий |
| 150 | 2 | Apple 10 60 200 Cherry 20 70 50 |
Sorry, we are closed for today | Объем фруктов на складе меньше 300. |
| 80 | 8 |
Dragonfruit 123 50 10 Aplle 10 60 200 Cherry 40 80 100 Coconut 20 5 30 Pineapple 80 90 50 Raspberry 70 95 30 Blackberry 130 95 30 Strawberry 60 95 40 Grape 20 95 120 Orange 10 80 200 Melon 10 98 300 Banana 20 30 120 |
Apple 80 800 | В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее. |
| 80 | 14 | (см. тест № 2) | Banana 40.000000 Raspberry 30.000000 Pineapple 10.000000 3700 |
Корректно |
| 110 | 1 | (см. тест №2) | Melon 110 1100 | Корректно |
Анализ задачи
- Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
- Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].
Алгоритм решения
-
- Объявить структуру [latex]fruit[/latex] с переменными:
- name
- specific_cost
- percentage
- amount
- Необходимо
- считывать информацию о фрукте;
- сортировать фрукты по некоторому параметру
Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.
- Объявить структуру [latex]fruit[/latex] с переменными:
- Дальнейшее решение распадается на несколько подзадач:
- Сортировка элементов вектора в порядке убывания стоимости единицы объема.
- Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
- Составление коктейля наименьшей стоимости при заданном объёме порции.
Был намечен следующий алгоритм действий:
- После сортировки определить, какая масса фруктов должна быть израсходована к моменту заказа, и последовательно проходить по вектору, уменьшая количество каждого фрукта, пока не дойдем до требуемого значения.
- Если оставшихся фруктов достаточно для приготовления коктейля, последовательно перерабатывать фрукты, пока на складе не закончится текущее наименование, а тогда перейти к следующему, и так пока не прийдем к заданному объему.
- На каждом шаге добавлять в рецепт количество использованных фруктов вместе с их названиями. В конце рецепта указать стоимость коктейля.
Программный код
Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; struct fruit{ string name; //название фрукта double specific_cost; //удельная стоимость double percentage; //процентный выход сока double amount; //текущее количество на складе double worth(){ //параметр в критерии отбора return (specific_cost * 100)/percentage; } bool get(){ //логический тип позволяет return (cin >> name //производить считывание >> specific_cost //до конца файла >> percentage >> amount); } }; int main() { double V; int n; //объем сока и номер посетителя по счёту cin >> V >> n; /*Заполнение меню - показателя текущего состояния на складе*/ vector<fruit> menu; fruit tmp; double total_amount = 0; while(tmp.get()){ menu.push_back(tmp); total_amount += tmp.amount; } /*Критерий отбора: отсортировать в порядке уменьшения цены за литр*/ sort(menu.begin(), menu.end(), [](fruit a, fruit b){return a.worth() < b.worth();}); /*Составление рецепта коктейля*/ /*1. Поиск фруктов, доступных на n-м шаге*/ double used = (n - 1) * V; int starting_position = 0; if(total_amount >= n*V && any_of(menu.begin(), menu.end(), [&](fruit &a) mutable { double new_amount = (used -= a.amount); if(new_wolume >= 0){starting_position++; a.amount = 0;} else a.amount = (-1)*new_amount; return new_amount < 0; })){ //Заполнение коктейля соком до заданного объёма double volume_left = V, price = 0; string recipe; /*Добавлять ингредиенты из отсортированного меню, пока возможно*/ any_of(menu.begin() + starting_position, menu.end(), [&](fruit &a) mutable { /*Если ингридиент израсходован*/ double new_amount = (volume_left -= a.amount); if(new_amount >= 0){ price += a.specific_cost * a.amount; recipe += a.name + ' ' + to_string(a.amount) + '\n'; a.amount = 0; } /*Если коктейль готов*/ else{ a.amount = new_amount + a.amount; price += a.specific_cost * a.amount; recipe += a.name + ' ' + to_string(a.amount) + '\n'; } return (new_amount <= 0); }); cout << recipe << price << endl; } else cout << "Sorry, we are closed for today." << endl; return 0; } |
Подробности реализации
Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.
- После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
- Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
- Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
- Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
- В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].
Зачтено