这题我用二分插入法都过了，可是这个算法似乎是 $\mathcal O(n^2)$ 的啊。怎么回事呢？数据不够强吗？

代码（C++）：

#include <iostream>

using namespace std;

inline int findLarger(int* arr, int size, int num)
{
    int lpos = 0, rpos = 0, cpos = 0;
    if (size == 0)
        return 0;
    else if (arr[size - 1] <= num)
        return size;
    lpos = 0;
    rpos = size - 1;
    while (rpos - lpos > 1)
    {
        cpos = (lpos + rpos) / 2;
        if (arr[cpos] > num)
            rpos = cpos;
        else if (arr[cpos] < num)
            lpos = cpos;
        else if (arr[cpos] == num)
            return cpos;
    }
    return rpos;
}

inline void insert(int* arr, int& size, int where, int item)
{
    int i = 0;
    for (i = size - 1; i >= where; --i)
        arr[i + 1] = arr[i];
    arr[where] = item;
    ++size;
}

int main()
{
    int n = 0, i = 0, j = 0, num = 0, * arrA = nullptr, * arrB = nullptr;
    int* mins = nullptr, minssize = 0;
    bool breaking = false;
    cin >> n;
    arrA = new int[n];
    arrB = new int[n];
    for (; i < n; ++i)
        cin >> arrA[i];
    for (i = 0; i < n; ++i)
        cin >> arrB[i];
    mins = new int[n + 1];
    for (i = 0; i < n; ++i)
    {
        breaking = true;
        for (j = 0; j <= i; ++j)
        {
            num = arrA[j] + arrB[i - j];
            if (minssize < n || num <= mins[n - 1])
            {
                breaking = false;
                insert(mins, minssize, findLarger(mins, minssize, num), num);
                if (minssize > n)
                    --minssize;
            }
        }
        if (breaking)
            break;
    }
    for (i = 0; i < n; ++i)
        if (i == 0)
            cout << mins[i];
        else
            cout << ' ' << mins[i];
    cout << endl;
    return 0;
}

备注：这个代码是我初来乍到时写的，可能跟现在的代码风格有点不同。当时也不会用 STL 的二分查找函数，手写了一个 findLarger 函数。