Решение задачи "Сделай равными" с Codeforces

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


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

Вы можете выбрать любое неотрицательное целое число D (т.е. D≥0) и для каждого ai совершить одно из следующих действий:

прибавить D (только один раз), т.е. выполнить ai:=ai+D;
вычесть D (только один раз), т.е. выполнить ai:=ai−D;
оставить значение ai без изменения.
Возможно, что после какой-либо операции значение какого-либо ai может стать отрицательным.

Ваша задача выбрать такое минимальное неотрицательное целое D и выполнить последовательность действий, что все ai станут равными (т.е. a1=a2=⋯=an).

Выведите искомое D или, если требуемое D найти невозможно, выведите -1.

Например, для массива [2,8] значение D=3 является минимально возможным, потому что Вы можете получить массив [5,5], если Вы добавите D к 2 и вычтете D из 8. А для массива [1,4,7,7] значение D=3 также является минимально возможным. Вы можете добавить его к 1 и вычесть его из 7 и получить массив [4,4,4,4].

Код

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int v[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    sort(v+1,v+n+1);
    int x=v[1]+v[n];
    if(x%2==1)
    {
        x=v[n];
    }
    else
    x/=2;
    for(int i=2;i<n;i++)
    {
        if(v[i]!=v[1]&&v[i]!=v[n]&&v[i]!=x)
        {
            cout<<-1;
            return 0;
        }
    }
    cout<<x-v[1];
    return 0;
}

         

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


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

Комментарии

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