Codeforces 1941A题：含sort()函数时答案错误的原因咨询

你在解决Codeforces 1941A《Rudolf and the ticket》时遇到了一个诡异的问题：移除代码中的两个sort()函数后程序输出正确，但保留排序时答案错误。明明排序没有改变数组元素的取值，却影响了最终结果，你的代码如下：

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    
    while(t--){
        int n, m, k, count = 0;
        cin >> n >> m >> k;
        int A[1000], B[1000];
        for (int i = 0; i < n; i++){
            cin >> A[i];
        }
        for(int i = 0; i < m; i++){
            cin >> B[i];
        }
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(A[i] + B[j] <= k){
                    count++;
                }
                
            }
        }
        cout << count << endl;
    }
}

问题根源 #

问题出在数组的初始化和排序范围上：

• 你声明了固定大小为1000的数组A和B，但实际只输入了前n和m个元素，数组中剩下的1000-n和1000-m个元素是未初始化的垃圾值（可能是随机的正数、负数或零）。
• 当你使用sort(begin(A), end(A))时，排序的是整个1000个元素，包括那些未初始化的垃圾值。排序后，原来的有效元素会和垃圾值混排，导致你后续循环遍历的前n个元素中，可能包含垃圾值，而原本的有效元素被挤到了数组的后半部分（没被遍历到）。
• 不排序的时候，你只遍历了前n和m个有效元素，后面的垃圾值没被访问，所以结果正确。

解决方法 #

有两种简单的修复方式：

• 缩小排序范围：只对输入的有效元素排序，把sort(begin(A), end(A))改成sort(A, A + n)，sort(begin(B), end(B))改成sort(B, B + m)。这样只会排序前n和m个有效元素，不会碰后面的垃圾值。
• 使用动态数组：把固定数组换成vector<int>，这样数组大小会自动匹配输入的元素个数，排序整个vector也不会有问题。比如：

  vector<int> A(n), B(m);
  // 输入逻辑不变
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  

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