Матч 379, Продажа продуктов (SellingProducts)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Вы продвигаете новый продукт на рынок. Ячейка price[i] содержит наибольшую цену, которую готов платить i - ый покупатель за Ваш товар, а cost[i] содержит стоимость доставки товара до i - го покупателя. Вам необходимо найти такую цену товара, при которой прибыль будет наибольшей. Если существует несколько цен, при которых прибыль наибольшая, то вернуть наименьшую цену.

Класс: SellingProducts

Метод: int optimalPrice(vector<int> price, vector<int> cost)

Ограничения: 1 £ length, width, height £ 10⁶, cubes содержит от 1 до 20 элементов, 1 £ cubes[i] £ 10⁶.

Вход. Массив price содержит цены покупателей на Ваш товар, массив cost содержит стоимость доставки товара покупателей.

Выход. Наименьшая цена товара, при которой прибыль будет наибольшей.

Пример входа

price	cost
{13,22,35}	{0,0,0}
{13,22,35}	{5,15,30}
{13,17,14,30,19,17,55,16}	{12,1,5,10,3,2,40,19}

Пример выхода

22

13

17

РЕШЕНИЕ

полный перебор

Для нахождения оптимального значения цены товара перебираем в ее качестве все значения cur_Price = price[i]. Для каждой такой цены в переменной s подсчитываем прибыль. Если текущая полученная прибыль s больше максимальной MaxProfit, то устанавливаем MaxProfit = s. Отдельно рассматриваем случай, когда текущая прибыль s равна максимальной MaxProfit, но при этом текущая цена товара cur_Price меньше opt_Price, на которой достигалась прибыль MaxProfit.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class SellingProducts

{

public:

int optimalPrice(vector<int> price, vector<int> cost)

{

int i, j, s, MaxProfit, cur_Price, opt_Price;

for(opt_Price = MaxProfit = i = 0; i < price.size(); i++)

{

cur_Price = price[i];

for(s = j = 0; j < price.size(); j++)

if (price[j] >= cur_Price)

s += max(0,cur_Price - cost[j]);

if (s > MaxProfit) MaxProfit = s,opt_Price = cur_Price; else

if ((s == MaxProfit) && (cur_Price < opt_Price)) opt_Price = cur_Price;

}

return opt_Price;

}

};