D. Extreme Subtraction
给出一个长度为n的数组
有两种操作:
1.选择一个前缀 将所有元素-1
2.选择一个后缀 将所有元素-1
问是否能将原数组变为全0数组
对数组的区间操作 联想到差分前缀
于是将原数组 转化成与它等价的差分数组
那么对原矩阵的区间操作就变成了对差分矩阵的两个端点操作:
将 $arr_1$-1 同时将 $arr_{i+1}$ +1
等价为将差分数组中某个负数变为0 同时将$arr_1$减小相同的量
将$arr_i$-1 同时将$arr_{n+1}$+1
等价为将差分数组中某个正数变为0 同时将$arr_n$变大(实际上我们不关心$arr_n$)
发现 若能通过上述两个操作将差分数组变为全0数组 那么还原成原数组就为全0数组
于是 直接判断若差分数组中$arr_1$ 足矣”填平”数组中所有负数 那么就输出YES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define endl '\n' #define Turnoff std::ios::sync_with_stdio(false) #define P pair<ll,ll> const int Max=3e5+5; const int Mod=998244353; const int inf=1e8;
ll diff[Max],arr[Max]; int main(){ Turnoff; int t;cin>>t; while(t--){ int n;cin>>n; diff[0]=diff[n+1]=0; for(int i=1;i<=n;i++){ cin>>arr[i]; diff[i]=arr[i]-arr[i-1]; } ll sum=0; for(int i=1;i<=n;i++){ if(diff[i]<0)sum+=diff[i]; } if(sum+arr[1]<0)cout<<"NO"<<endl; else cout<<"YES"<<endl;
}
}
|