# Greedy Florist

See the original problem on HackerRank.

We first need to sort the price of flowers in decreasing order, and then distribute these flowers evenly amongst our friends buying the most expensive first.

Solution in C++:

 1 2 3 4 5 6 7 8  int N, K; cin >> N >> K; vector c; c.reserve(N); copy_n(istream_iterator(cin), N, back_inserter(c)); sort(begin(c), end(c), greater()); cout << accumulate(begin(c), end(c), 0, [=,count=0](int res, int curr) mutable { return res + curr * (count++ / K + 1); }); 

Solution in C# by Simone Busoli:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  static Func> ReadNumbers = () => ReadLine().Split(' ').Select(int.Parse); static void Main(String[] args) { var k = ReadNumbers().Last(); var costs = ReadNumbers(); WriteLine(costs.OrderByDescending(x => x) .Select((f, i) => new {f,i}) .GroupBy(t => t.i/k) .Select((g, i) => g.Select(t => t.f * (i+1)).Sum()) .Sum()); } } 

Solution in Haskell by Alessandro Pezzato

  1 2 3 4 5 6 7 8 9 10 11 12 13  import Data.List (sortBy) minimumCost :: Int -> Int -> [Int] -> Int minimumCost _ _ [] = 0 minimumCost k m c = t + minimumCost k m' c' where m' = m + 1 c' = drop k c t = sum $(* m) <$> take k c main = do _:k:c <- fmap read . words <$> getContents print$ minimumCost k 1 \$ sortBy (flip compare) c 

Alternative solution using a priority queue:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int N, K, price; cin >> N >> K; long long int totalAmount = 0; priority_queue prices; for(int i = 0; i < N; i++) { cin >> price; prices.push(price); } int x; for (x = 0; x < N; ++x) { totalAmount += (x / K + 1) * prices.top(); prices.pop(); } cout << totalAmount << "\n"; 
We've worked on this challenge in these gyms: modena  turin  padua