PROBLEM LINK: Avinash The Mafia
DIFFICULTY:
SIMPLE-EASY.
PREREQUISITES:
Greedy, Math , Prefix sum
PROBLEM:
There are N rooms in hostel and i_{th} room has A_i worth of gold coins , where 1 ≤ i ≤ N. You have to apply following operation until all the N rooms in hostel have been selected:
- Select a room which hasn’t been selected yet, pay A_i money for all the gold coins.
- Select atmost K rooms which hasn’t been selected yet, and pay nothing.
You have to determine minimum amount required to select all the N rooms in hostel.
QUICK EXPLANATION:
Observe the greedy setting in this problem. In every operation you have to pay for only one room and then you can get everything for free for rest K rooms.
EXPLANATION:
This is the greedy approach: Since we are required to pay for one room in every operation , we will ensure that this is the room which has the least possible value of gold coins. After that we can loot atmost K rooms for free, so we will ensure that these are the rooms with maximum worth of gold coins.
Now in every operation we select atmost (K+1) rooms in hostel. So number of
times we have to perform the above operation will be \left\lceil \frac{N}{K+1} \right\rceil, let this be x.
Now as we know that we are going to perform x number of operations, that means we are going to pay x number of times.
It makes sense to sort the initial array before answering queries.
Subtask #1:
In this version of problem you can simply simulate the whole operation using two pointer method. Start by selecting a room of minimum value then select K maximum values. Do this until all the rooms are not selected.
Time Complexity:
Time Complexity of this approach is O(NlogN + N*T). NLogN for sorting the array and N*T for answering the query.
Subtask #2:
In this version of problem you can improve the complexity of code by the use of prefix sum , where pre[i] = sum of values of gold coins from room 1 to room i.
Now we can answer the queries in O(1). Where ans = pre[x-1] (0-indexing).
Time Complexity:
Time Complexity of this approach is O(NlogN + T). NLogN for sorting the array and T for answering the query.
SOLUTIONS:
Subtask #1:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
ll n;
cin >> n;
ll a[n];
for (ll i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
cin >> t;
while (t--)
{
ll i, j, k, m;
cin >> k;
ll ans = 0;
i = 0, j = n - 1;
while (i <= j)
{
ans += a[i];
ll v = k;
while (i < j && v--)
j--;
i++;
}
cout << ans << "\n";
}
return 0;
}
Subtask #2:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
ll n;
cin >> n;
ll a[n], s = 0;
for (ll i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
ll pre[n];
for (ll i = 0; i < n; i++)
{
s += a[i];
pre[i] = s;
}
cin >> t;
while (t--)
{
ll i, j, k, m;
cin >> k;
ll x = (n + k) / (k + 1); //ceil(N/(K+1))
cout << pre[x - 1] << "\n";
}
return 0;
}