CF 1443D Extreme Subtraction

题目描述

https://codeforces.com/contest/1443/problem/D

Solution

注意到操作的顺序可以互换，那么我们可以先做从右边减的，再做从左边减的

注意到只有左操作的时候，所能减的序列一定是非降的

那么现在问题转换成用一个非增的序列减原序列得到一个非降的序列

我们考虑构造这个非增的序列

注意到一共能减的次数是 $a[n]$，我们倒叙遍历 $a$，如果 $a[i]>a[i-1]$，意味着我们必须要减掉多余的部分

当次数用完且出现不合法的情况时无解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define maxn 30010
#define gc getchar
#define cn const node
#define cQ const Queue
#define INF 1000000000
#define ll long long
#define cS const Seg
using namespace std;

int n, a[maxn];

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int sum = a[n];
    for (int i = n; i > 1; --i) {
        if (a[i - 1] >= a[i]) continue;
        sum -= a[i] - a[i - 1];
        if (sum < 0) return (void) puts("NO");
    }
    puts("YES");   
} 

int main() {
    int T; cin >> T;
    while (T--) work(); 
    return 0;
}