CF1713B

Ender_hz · 2022-08-14 00:31:36 · 题解

题意

给定一个长度为 n(1\le n\le10^5) 的数组 a，你可以进行若干次操作，每次操作，你可以选择两个数 l,r(1\le l \le r \le n)，让 a_l,a_{l+1},\cdots,a_r 各自减 1，记 f(a) 为使数组 a 的每个元素均变成 0 所需要的最小操作次数，请你判断对于 a 打乱后的任意排列 b，是否有 f(a)\le f(b) 恒成立。

分析

我们不妨考虑数组 a 打乱后的任意排列中（包括 a 本身），函数 f 的最小值以及取到最小值需要的条件。

由于数组的末状态为每个元素均为 0，所以不可能对已经等于 0 的元素进行操作；又因为每次操作选择的都是连续区间，所以应该保证操作后 0 一定出现在数组的两端（或一端）。

为了满足上述条件，不难想到原数组应满足的条件：由一段非严格单调递增序列和一段非严格单调递减序列构成，或由两者之一构成；这时 f 函数取到最小值，即 \max(a_i)。

满足这样的排列有很多种，我们只需判断 a 数组是否满足上述条件即可。

代码

#include<iostream>
#define sfor(i, h, t) for(int i = (h); i <= (t); ++i)
using namespace std;
const int MAXN = 0x186A8;
int T = 1, N;
int num[MAXN];
signed main(void) {
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> N;
        bool f = 0, g = 0;
        sfor(i, 1, N) {
            cin >> num[i];
            if(g)
                continue;
            if(!f)
                if(num[i] < num[i - 1])
                    f = 1;
            if(f)
                if(num[i] > num[i - 1])
                    g = 1;
        }
        cout << (g ? "NO\n" : "YES\n");
    }
    return 0;
}