题解：CF2060D Subtract Min Sort

guoguo160 · 2025-01-25 16:29:40 · 题解

题解：CF2060D Subtract Min Sort

前言

UPD 2025.10.6: 修正了晦涩难懂的语言，避免歧义。

题意

每次选择两个相邻的数并减去其中的最小值，问能否通过若干次操作让数列单调不降。

思路

赛时是猜的结论。

贪心的去想，感性理解，如果我们要使得一个序列单调不降，肯定让前面的数尽量小一点点，那么考虑对两个相邻的数进行一次操作，肯定会让两个数都变小或者不变，所以进行操作是最好的，我们只需要对于每一对数进行操作就好了。

代码实现

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int N = 2 * 1e5 + 10;

int n;
int a[N];
int t;

signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1;i <= n;++i) {
            cin >> a[i];
        }
        for (int i = 2;i <= n;++i) {
            int t = min(a[i - 1]，a[i]);
            a[i - 1] -= t;
            a[i] -= t;
        }
        bool flg = false;
        for (int i = 2;i <= n;++i) {
            if (a[i] < a[i - 1]) {
                cout << "NO\n";
                flg = true;
            }
            if (flg) break;
        }
        if (flg) continue;
        cout << "Yes\n";
    }
    return 0;
}

后记

一个小小的附加题。

如果我们要让这个序列单调不降呢？

留给大家自己思考，换汤不换药。