Google Kick Start 2020 Round A Allocation题WA错误排查求助

你的思路完全正确——先排序再从小到大选购房屋，直到预算不足，但代码里有几个容易被忽略的边界问题和潜在风险，导致提交时出现Wrong Answer：

1. 数组越界访问 #

你的while循环里没有检查i是否超出数组长度。比如当预算B足够买下所有N套房子时，i会一直递增到等于size，这时候访问prices[i]就属于越界读取，会拿到内存里的垃圾值，导致cur_total + prices[i] <= b的判断出错，要么提前终止循环，要么触发未定义行为，最终输出错误的计数。

2. 整数溢出风险 #

cur_total是int类型，如果房屋总价超过了int的最大值（比如遇到大量高价房屋的测试用例），会发生整数溢出，cur_total会变成负数。这时候负数加房屋价格可能依然满足<= b的条件，导致循环继续执行，计数错误。

修正后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int tests;
    cin >> tests;
    
    for (int j = 0; j < tests; ++j) {
        int N, B;
        cin >> N >> B;
        
        vector<int> prices(N);
        for (int i = 0; i < N; ++i) {
            cin >> prices[i];
        }
        
        sort(prices.begin(), prices.end());
        
        long long cur_total = 0; // 用long long避免溢出
        int count = 0;
        
        for (int i = 0; i < N; ++i) { // 用for循环天然限制i的范围，避免越界
            if (cur_total + prices[i] <= B) {
                cur_total += prices[i];
                count++;
            } else {
                break;
            }
        }
        
        cout << "Case #" << j + 1 << ": " << count << endl;
    }
    return 0;
}

关键修改点 #

• 把while循环改成for循环，直接遍历数组的每个元素，从根本上避免越界问题；
• 将cur_total的类型改为long long，防止总价超出int范围导致溢出；
• 统一变量类型（比如用int表示N、循环索引i），避免无符号/有符号类型混用的潜在问题；
• 显式写出必要的头文件（原代码可能依赖编译器隐式包含，但提交时需要显式声明才能保证兼容性）。

这些修改应该能解决你遇到的WA问题，你可以试试提交这个版本。

内容的提问来源于stack exchange，提问作者Younse Park