[Extremely Easy] P12113 [NWRRC2024] If I Could Turn Back Time

很怀疑出题人的精神状态 +1。注意到题目给出的山峰侵蚀操作满足下面两个性质：

• 操作是保序的（指无论进行多少次山峰侵蚀操作，若定义全序关系 $\preceq$ 为 $\leq$，则两座山峰的高度的关系始终不变）。
• 操作是单调的（指无论进行多少次山峰侵蚀操作，原本高度高的山峰，被侵蚀的次数一定比高度低的山峰多）。

于是根据这两个性质，我们只需要将序列按照 $h$ 为第一关键字，$w$ 为第二关键字排序，依次检验一下是否满足操作次数单调即可。最后的答案就是所有山峰的操作次数最大值。时间复杂度 $O(\sum n\log n)$。

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

const int N = 1e5 + 5;
int n, a[N], b[N], p[N];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    iota(p + 1, p + n + 1, 1);
    sort(p + 1, p + n + 1, [](int x, int y){
        return a[x] == a[y] ? b[x] < b[y] : a[x] < a[y];
    });
    int lst = 0;
    for(int i=1;i<=n;i++){
        if(lst > b[p[i]] - a[p[i]]) return cout << "-1\n", void();
        lst = b[p[i]] - a[p[i]];
    }
    cout << lst << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

// Written by xiezheyuan

QOJ Submission。