Mark and Toys · Coding Gym

Solutions

Since we need to maximize the number of toys, we can sort the array in incresing order of price and pick them as long as the budget is available.

A solution in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include <iterator>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, k; cin >> n >> k;
    vector<int> prices(n);
    copy_n(istream_iterator<int>(cin), n, begin(prices));
    sort(begin(prices), end(prices));
    auto toys = 0, cost=0;
    for (auto i=0u; i<prices.size() && cost<=k; ++i)
    {
        if (prices[i]+cost<=k)
        {
            cost+=prices[i];
            ++toys;
        }
    }
    cout << toys << endl;
}

In Haskell:

1
2
3
4
5
6
7
8
9


import Data.List (sort)

keepWhileSumBelow k = foldl (\l x -> if sum (x:l) < k then x:l else l) []
maximumToys prices k = length $ keepWhileSumBelow k $ sort prices

main = do
    contents <- getContents
    let (_:k:prices) = map read $ words contents
    print $ maximumToys prices k

Using heap operations

An alternative solution consists in maintaining a min heap:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> prices;

    for (int i = 0; i < n; i++) 
    {
        int price_item; cin >> price_item;

        auto sum = accumulate(begin(prices), end(prices), 0);

        if (sum + price_item <= k) 
        {
            prices.push_back(price_item);
            push_heap(begin(prices), end(prices));
        } 
        else if (sum) 
        {
            pop_heap(begin(prices), end(prices));
            auto last = prices.rbegin();
            *last = min(*last, price_item);
            push_heap(begin(prices), end(prices));
        }
    }

    cout << prices.size() << "\n";
}

sort