Решение задачи "День рождения Мотарака" с Codeforces

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


Дарк собирается посетить день рождения Мотарака. Дарк решил, что он хочет подарить Мотараку массив a, состоящий из n неотрицательных целых чисел.

Дарк создал этот массив еще 1000 лет назад, поэтому некоторые его элементы пропали. Дарк знает, что Мотарак не любит, когда у двух соседних элементов большая абсолютная разница. У него не так много времени, поэтому он хочет выбрать целое число k (0≤k≤109) и заменить все пропущенные элементы в массиве a числом k.

Обозначим за m максимальную абсолютную разницу между всеми парами соседних элементов (то есть максимальное значение |ai−ai+1| по всем 1≤i≤n−1) в массиве a после того, как Дарк заменит все пропавшие элементы на число k.

Дарк хочет выбрать число k так, что m будет минимально. Можете ли вы помочь ему?

Код

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int a[1000005];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		int Max=0,Min=1000000000,ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=2;i<=n;i++)
			if(a[i]==-1) Max=max(Max,a[i-1]),Min=(a[i-1]==-1)?Min:min(Min,a[i-1]);
		for(int i=1;i<n;i++)
			if(a[i]==-1) Max=max(Max,a[i+1]),Min=(a[i+1]==-1)?Min:min(Min,a[i+1]);
		for(int i=1;i<n;i++)
			if(a[i]!=-1&&a[i+1]!=-1) ans=max(ans,abs(a[i+1]-a[i]));
		ans=max(ans,(Max-Min+1)/2);
		printf("%d %d\n",ans,(Max+Min)/2);
	}
}

         

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


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

Комментарии

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