时间戳

首页 > 解决方案 > Google Kickstart 2020 Round A 错误答案：我的代码有什么问题？

c++ - Google Kickstart 2020 Round A 错误答案：我的代码有什么问题？

问题描述

有 N 栋房屋待售。第 i 间房子花费 Ai 美元购买。你有 B 美元的预算要花。最多可以买多少套房子？

我的算法很简单。通过将所有房价添加到由优先级队列表示的最小堆中来对所有房价进行排序，然后将价格从队列中弹出（在您这样做时计数），直到您达到预算。

所以我真的不知道为什么我的代码甚至不能通过第一个测试用例。任何建议将不胜感激！

在此处输入图像描述

这是我的代码：

    #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;
    }

（此外，我已将问题提示附加为图像，因为过去我曾因将问题与问题提示混淆在一起而受到批评，但如果我选择的这种格式不好，请告诉我）

标签： c++algorithmsorting

解决方案

有几件事可能会让你失望：

正如vivek_23所提到while(sum < B)的，如果我们可以用我们的预算购买所有房屋，这个循环将出现运行时错误，请将其while(sum < B && !pq.empty())改为。

此外，您在两个嵌套循环中都使用相同的变量i将其更改为其他内容

推荐阅读