Problem - 1716B - Codeforces
codeforces.com
- 제목
Optimal Reduction
- 조건
time limit per test : 1 second
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
Consider an array a of n positive integers.
You may perform the following operation:
select two indices l and r (1≤l≤r≤n), then
decrease all elements al,al+1,…,ar by 1.
Let's call f(a) the minimum number of operations needed to change array a into an array of n zeros.
Determine if for all permutations† b of a, f(a)≤f(b) is true.
† An array b is a permutation of an array a if b consists of the elements of a in arbitrary order. For example, [4,2,3,4] is a permutation of [3,2,4,4] while [1,2,2] is not a permutation of [1,2,3].
- 입력
The first line contains a single integer t (1≤t≤10^4) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤10^5) — the length of the array a.
The second line contains n integers a1,a2,…,an (1≤ai≤10^9) — description of the array a.
It is guaranteed that the sum of n over all test cases does not exceed 10^5.
- 출력
For each test case, print "YES" (without quotes) if for all permutations b of a, f(a)≤f(b) is true, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
| 예제 입력1 | 예제 출력1 |
| 3 4 2 3 5 4 3 1 2 3 4 3 1 3 2 |
YES YES NO |
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, sz;
cin >> tc;
while(tc--){
cin >> sz;
int *arr = new int[sz];
bool down = false;
bool v = false;
for(int n = 0 ; n < sz ; n++){
cin >> arr[n];
if(n > 0){
if(down && arr[n - 1] < arr[n]){
v = true;
continue;
}
if(arr[n - 1] > arr[n]){
down = true;
}
}
}
if(v) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}