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<int> c; c.reserve(N);
copy_n(istream_iterator<int>(cin), N, back_inserter(c));
sort(begin(c), end(c), greater<int>());
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<IEnumerable<int>> 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<int> 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 
comments powered by Disqus