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