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";
|