Участник:Qwerty/копейка рубль бережёт

Материал из DISCOPAL
Перейти к: навигация, поиск

Алгоритм.

Вначале просуммируем все стоимости товаров в корзине.

Получилось число с дробной частью .

Если дробная часть не равна нулю - делим дробную часть на всю стоимость - находим долю в дробной части

от всей стоимости всех товаров.

Находим её в процентном соотношении - и делаем скидку на ВСЕ товары одинаковую.


StasFomin (обсуждение) 06:53, 6 апреля 2017 (UTC): Не понял. Распишите алгоритм. Но точно уверен, что неверно. Пока у вас не появится элементов динамического программирования, решение точно неверно. Перечитайте формулировку. Представьте корзину

колво  цена
 97    0руб 99коп

...

 77    0руб 97коп

Вы точно готовы сказать, как оптимально округлить ЦЕНЫ? (округляются только ЦЕНЫ, не стоимости в каждой строке).



Но в условии не сказано про округлить цены, в условии надо получить целочисленную сумму


Окей, если мы должны сделать скидку на ЦЕНЫ, тогда сначала делаем "скидку" на стоимость строки, потом делим её на количество товаров в строке, и получаем Скидку




Иначе, пускай s = [s] + {s}.

(skidka)*s = skidka *(sum товаров ) = sum ( товар*skidka ) = [s] - целое число.

Алгоритм корректен, так как мы нашли БЛИЖАЙШЕЕ левое целое число к числу [s] + {s} - любое другое решение будет вида [s] - K, K - натуральное больше нуля

Суммирование - линейное время

Нахождение доли (деление) -считаем, что за константное время (арифметическая операция)

Умножить соответственно все цены - также линейное время

Профит.