3 months ago

Swapnil Soni • 0

Vasco da Gama

Q31)

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

int solve(int x,int n,vector<int>& arr){
  priority_queue<int,vector<int>,greater<int>> pq;
  for(auto &it: arr)
    pq.push(it);
 
  int cnt = 0;
 
  while(pq.size()>1){
      int mn1 = pq.top();
      pq.pop();
      if(mn1 >= x)
        break;
      int mn2 = pq.top();
      pq.pop();
      
      pq.push(mn1 + 2*mn2);
      cnt++;
  }
 
  if(pq.top() < x)
    return -1;
 
  return cnt;
}

int main()
{   
    int x;
    cin>>x;
    
    int n;
    cin>>n;
    
    vector<int> arr(n);
    
    for(int i=0;i<n;i++)
      cin>>arr[i];
    
    cout<<solve(x,n,arr);
    
    return 0;
}