Решение задачи Заострение массива с Codeforces

Без пояснения   Просмотров: 45


Вам дан массив a1,…,an из n неотрицательных целых чисел.

Назовем его заостренным, если существует целое число 1≤k≤n, такое что a1ak+1>…>an. В частности, любой строго возрастающий или строго убывающий массив является заостренным. Например:

Массивы [4], [0,1], [12,10,8] и [3,11,15,9,7,4] являются заостренными;
Массивы [2,8,2,8,6,5], [0,1,1,0] и [2,5,6,9,8,8] не являются заостренными.
Вы можете сделать следующую операцию, сколько угодно раз: выбрать любой строго положительный элемент массива и уменьшить его на единицу. Формально, вы можете выбрать любой индекс i (1≤i≤n), такой что ai>0, и выполнить присвоение ai:=ai−1.

Определите, возможно ли сделать данный массив заостренным, сделав некоторое количество (возможно ноль) этих операций.

Код

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int T, n, a[N];
int main () {
	scanf ("%d", &T);
	while (T --) {
		scanf ("%d", &n);
		for (int i = 1; i <= n; i ++)
			scanf ("%d", &a[i]);
		int l = 1, r = n;
		while (a[l + 1] >= l)
			l ++;
		while (a[r - 1] >= n - r + 1)
			r --;
		if (l >= r)
			puts ("Yes");
		else
			puts ("No");
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться