PLAG02 - Editorial

PROBLEM LINK:

PRACTICE
Editorialist: Yogesh Yogendra

DIFFICULTY:

HARD

PREREQUISITES:

Sorting, Map

PROBLEM:

Chef wants to make his code plagiarism-free so he went to Chefina for help for making his code plagiarism-free. Chefina told him that she will help him if he do a task for her. Chefina explained to him the task.

Chef will be given NN bricks. Every brick is represented by a number which means that he can keep at most that number of bricks on top of it.
Chef’s task is to make pillars from the available bricks but there is one condition that he has to minimize the number of pillars. After making all the pillars he has to tell the total number of pillars he made.

EXPLANATION:

As in this question, we can see that we have to find the minimum number of pillars so
we can use the brute force soln as the constraints were very less.

SOLUTION:

#include<bits/stdc++.h>
#define int long long int
using namespace std;

void FIO(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

void solve(){
	
    int t;
    cin>>t;
    while(t--){
    	int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++) cin>>a[i];
	    sort(a,a+n);
	    map<int,int> m;
	    int used = 0;
	    int ans = 0;
	    int h = 0;
	    while(true){
	        if(used == n) break;
	        ans++;
	        h = 0;
	        for(int i=0;i<n;i++){
	            if(!m[i] and a[i]>=h){
	                h++;
	                m[i] = 1;
	                used++;
	            }
	        }
	    }
	    cout<<ans;
    }

}

int32_t main()
{
	FIO();
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	solve();
	
	return 0;
}