Positive Array Codechef contest Problem Solution

A 1-indexed array is called positive if every element of the array is greater than or equal to the index on which it lies. Formally, an array of size is called positive if for each .

For example, the arrays are positive while the arrays are not positive.

You are given an array containing integers. You want to distribute all elements of the array into some positive arrays. The elements of a positive array might not occur in the order they appear in the array .

Find the minimum number of positive arrays that the elements of the array can be divided into.

Please see the sample cases below for more clarity.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains an integer — the number of elements in the array
    • The next line contains space-separated integers — the elements of array

      Output Format

      For each test case, output on a new line the minimum number of positive arrays that the elements of the array can be divided into.

      Constraints

      • The sum of over all test cases won’t exceed

        Sample Input 1

        5
        3
        2 3 3
        4
        3 1 1 2
        3
        1 1 1
        5
        1 2 2 4 5
        6
        3 2 1 2 2 1
        

        Sample Output 1

        1
        2
        3
        2
        3
        

        Explanation

        Test case : The given array is already positive. So the optimal division is

        Test case : One possible division is

        Test case : The only possible division is

        Test case : One possible division is

        Test case : One possible division is .

        				
        					#include <bits/stdc++.h> 
        #define fastio ios_base::sync_with_stdio(false), cin.tie(NULL); 
        #define int long long 
        
        
        
        
        using namespace std; 
         
        void solve(){ 
            int n; 
            cin>>n; 
            int a[n]; 
            multiset<int> s; 
            for (int i=0;i<n;i++) { 
                cin>>a[i]; 
                s.insert(a[i]); 
            } 
            int res = 1, ptr = 1; 
            while (s.size()>0){ 
                auto i = s.lower_bound(ptr); 
                if (i!=s.end()){ 
                    // cout<<ptr<<" "<<*i<<endl; 
                    s.erase(i); 
                    ptr++; 
                } 
                else{ 
                    ptr = 1; 
                    res++; 
                } 
            } 
            cout<<res<<endl; 
        } 
         
        signed main(){ 
            #ifndef ONLINE_JUDGE 
                freopen("input.txt", "r", stdin); 
                freopen("output.txt", "w", stdout); 
            #endif 
            fastio 
            int t; 
            t = 1; 
            cin>>t; 
            while(t--){ 
          solve(); 
         } 
        }
        				
        			

        0 Comments

        Leave a Reply

        Avatar placeholder

        Your email address will not be published.