• + 0 comments

    I am using min heap to solve this problem

    #include <bits/stdc++.h>
    #define lli long long int
    using namespace std;
    
    struct greaters {
        bool operator() (const long&a, const long&b) const {
            return a > b;
        }
    };
    
    int main (int argc, char *argv[]) {
    
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    
        vector<int> v;
        lli ans = 0;
    
        lli n, k;
        cin >> n >> k;
        while(n--) {
            lli x;
            cin >> x;
            v.push_back(x);
        }
        // min heap
        make_heap(v.begin(), v.end(), greaters());
    		// check if there's a minimum element < k
        if (v.front() < k) {
            while(v.size() > 1) {
                int firstMinVal = v.front();
                // delete min heap
                pop_heap(v.begin(), v.end(), greaters());
                v.pop_back();
    
                int secondMinVal = v.front();
                // delete min heap
                pop_heap(v.begin(), v.end(), greaters());
                v.pop_back();
    
                int formula = firstMinVal + (2*secondMinVal);
    						// push heap
                v.push_back(formula);
                push_heap(v.begin(), v.end(), greaters());
    
                ans++;
    
                int minVal = v.front();
                if (minVal >= k) {
                    break;
                }
            }
        }
    
        if (v.size() == 1 && v.front() < k) {
            cout << -1 << "\n";
        } else {
            cout << ans << endl;
        }
    
    
        return 0;
    }