PROBLEM LINK:
Author: Shriram Chandran
Editorialist: Shriram Chandran
DIFFICULTY:
Easy
PREREQUISITES:
Greedy
PROBLEM:
Given a set of elements, find a maximum matching if any two elements can be paired if they are within twice of each other.
EXPLANATION:
Note that if we have i and j paired up and there is another person k with a_i \leq a_k \leq a_j, then both j and k can be paired and i and k can be paired.
Thus this gives us a greedy solution of maximizing number of teams at every index:
Sort the array in descending order.
Now at index i, if a_i \leq 2a_{i+1}, then pair i and i+1 and go to i+2. Otherwise, leave a_i and go to i+1.
All correct answers are given AC verdict.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ans;
void calc(pair<int,int> a[],int n)
{
if(n<=0)
return;
else if(a[n].first>2*a[n-1].first)
calc(a,n-1);
else
{
ans.push_back(make_pair(a[n].second,a[n-1].second));
calc(a,n-2);
}
}
void solve()
{
int n;
cin>>n;
pair<int,int> a[n];
for(int i=0;i<n;i++)
{
cin>>a[i].first;
a[i].second=i+1;
}
ans.clear();
sort(a,a+n);
calc(a,n-1);
cout<<2*ans.size()<<endl;
for(auto i:ans)
cout<<i.first<<" "<<i.second<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
