#priority queue

Solutions Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \). Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, t; cin >> n >> t; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto cnt = 0; for (auto i=0; i<n; ++i) { if (t-v[i] < 0) break; t -= v[i]; cnt++; } cout << cnt; The solution is \( O(N \cdot logN) \). [Read More]

Solutions This is a classical problem whose typical solution involves employing two (differently ordered) heaps that maintain the two halves of the input arranged in a way that is convenient to retrieve the maximum of the former and the minimum of the latter. In other words, Consider this sample input: 1 10 1 5 7 9 3 Imagine we want to calculate the median of this array. We can see the array as: [Read More]

Solutions This problem is an application of the classical running median problem with a complication: the sliding window. The running median consists in calculating the median of all the subarrays from 0 to N. For example: 1 2 3 4 5 6 7 10 1 5 7 9 3 [10] -> 10 [10 1] -> (10+1)/2 [10 1 5] -> 5 [10 1 5 7] -> (5+7)/2 [10 1 5 7 9] -> 7 [10 1 5 7 9 3] -> (5+7)/2 The typical solution to this problem involves two (differently ordered) heaps that maintain the two halves of the input arranged in a way that is convenient to retrieve the maximum of the former and the minimum of the latter. [Read More]

Solutions This is a typical job for a priority queue. Basically, we maintain the least sweet cookie on top: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 priority_queue<int, deque<int>, greater<int>> cookies; while (N--) { cin >> tmp; cookies.push(tmp); } auto cnt = 0; while (cookies.size()>1 && cookies.top()<K) { const auto c1 = cookies.top(); cookies.pop(); const auto c2 = cookies.top(); cookies.pop(); cookies.push(c1 + 2*c2); ++cnt; } cout << ((cookies. [Read More]