Пятничная задача про бутылки и стаканы
Жалко стало стирать примерчик :) Как и в задаче алкоголика, предполагаем, что в стаканы налита вода или лимонад :)
Имеется n
стаканов, ёмкости которых могут быть различны и хранятся в массиве a
.
Задача состоит в том, чтобы разлить k≤n
стаканов, открыв при этом наименьшее количество бутылок.
Ёмкость всех бутылок одинакова и равна c
.
Идея решения очень проста - отсортировать ёмкости стаканов по возрастанию, затем сложить
первые k
ёмкостей и поделить на значение c
.
Встроенные в C++ стандартные алгоритмы позволяют обойтись без "школьного" ручного программирования сортировки и суммирования.
Вот мини-листинг, консоль Visual Studio (C++) 2015.
#include <iostream> #include <cmath> #include <algorithm> #include <numeric> #include <functional> int bottles(int n, int a[], int k, int c) { std::sort(a, a + n); int sum = std::accumulate(a, a + k, 0, std::plus<int>()); return ceil((double)sum / (double)c); } int main() { const int n = 5; //количество стаканов int a[n] = { 200, 200, 330, 100, 100 }; //емкости стаканов int k = 3; //сколько стаканов разлить int c = 500; //емкость бутылки std::cout << bottles (n, a, k ,c); //1 (100+100+200) std::cin.get(); return 0; }
02.11.2018, 15:05 [1516 просмотров]