【例83.1】 奥利凡德

解题思路

魔杖与盒子分别升序排序，对应位置检查Xi≤Yi。全部满足即可DA，否则NE。

正确性说明

若同序可配则给出直接可行方案。若某i处Xi>Yi，则至少n-i根长杖只能装进不足n-i个更长盒，无法一一装下，因此条件必要且充分。

易错点

每个盒只能一根；不是只比较两组总长度。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for (auto &v : x)
        cin >> v;
    for (auto &v : y)
        cin >> v;
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (x[i] > y[i])
            ok = false;
    cout << (ok ? "DA" : "NE") << "\n";
    return 0;
}