БлогNot. Пятничная задача про бутылки и стаканы

Пятничная задача про бутылки и стаканы

Жалко стало стирать примерчик :) Как и в задаче алкоголика, предполагаем, что в стаканы налита вода или лимонад :)

Имеется 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 [1514 просмотров]


теги: c++ числа алгоритм

К этой статье пока нет комментариев, Ваш будет первым