0

There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend. What is the maximum number of houses you can buy?

My algorithm is pretty simple. Sort all the house prices by adding them to a min heap represented by a priority queue, then pop prices off the queue (counting as you do so) until you've reached the budget.

So I'm really at a loss as to why my code can't even pass the first test case. Any advice would be greatly appreciated!

enter image description here

Here's my code:

    #include <iostream>
    #include <bits/stdc++.h> 
    using namespace std; 
        
    int main() {
      
      int t;
      cin >> t; // read t. cin knows that t is an int, so it reads it as such.
      
      for (int i = 1; i <= t; ++i) {
          
         int N, B;
         cin >> N >> B;
         
         priority_queue <int, vector<int>, greater<int> > pq; 
         
         for(int i=0; i<N; i++){
             int a;
             cin >> a; 
             pq.push(a);
         }
         
         long sum = 0;
         long count =0;
         
         while(sum < B){
             sum += pq.top();
             pq.pop();
             ++count;
         }
         
         if(sum > B){
             --count;
         }
          
        cout << "Case #" << i << ": " << count << endl;
      }
      return 0;
    }

(Also I've attached the problem prompt as an image because I've been criticized in the past before for cluttering up my question with the problem prompt but please let me know if this format that I've chosen is bad)

Shisui
  • 1,051
  • 1
  • 8
  • 23

1 Answers1

1

There's a few things that might be failing you:

As vivek_23 have mentioned while(sum < B) this loop will get runtime error if we can buy all houses with our budget, change it to while(sum < B && !pq.empty()) instead.

Also you are using same variable i in both nested loops change it to something else

Photon
  • 2,717
  • 1
  • 18
  • 22