# PROBLEM LINK: Avinash The Mafia

Fractal Code Fiesta

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.

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.

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:

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


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