Решение задачи Приравнивание цен с Codeforces

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


В магазине продается n предметов. Цена i-го предмета равна ai. Владелец магазина хочет приравнять цены всех предметов. Но он хочет изменить цены аккуратно.

Фактически, владелец магазина может изменять цену какого-то предмета i таким образом, что разница между старой ценой этого предмета ai и новой ценой bi не превышает k. Другими словами, должно выполняться условие |ai−bi|≤k (|x| — это абсолютное значение x).

Он может изменять цену каждого предмета не более одного раза. Заметьте, что он может оставить старые цены некоторым предметам. Новая цена bi каждого предмета i должна быть положительной (то есть должно выполняться условие bi>0 для всех i от 1 до n).

Ваша задача — найти максимально возможную равную цену B всех предметов с ограничением, что для всех предметов должно выполняться условие |ai−B|≤k (где ai равно старой цене предмета, а B — это одинаковая новая цена всех предметов) или сказать, что невозможно найти такую цену B.

Заметьте, что выбранная цена B должна быть целой.

Вам необходимо ответить на q независимых запросов.

Код

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[105];
int main(){
	int t;
	cin >> t;
	int n, k;
	while(t--){
		cin >> n >> k;
		for(int i = 1; i <= n; i++) 
            cin >> a[i];
		sort(a + 1, a + n + 1);
		if(a[n] - a[1] <= 2 * k) 
            cout << a[1] + k << endl;
		else 
            cout << "-1\n";
	}
	return 0;
} 

         

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



Комментарии

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