Решение задачи Честный тренер с Codeforces

С пояснением   Просмотров: 91


Перед вами стоит n спортсменов. Спортсмены пронумерованы от 1 до n слева направо. Про каждого спортсмена вы знаете его силу — спортсмен с номером i имеет силу si.

Вы хотите разделить всех спортсменов на две команды. В каждой команде должен быть хотя бы один спортсмен, и каждый спортсмен должен быть ровно в одной команде.

Вы хотите, чтобы самый сильный спортсмен из первой команды по силе как можно меньше отличался от самого слабого спортсмена из второй команды. Формально, вы хотите разделить спортсменов на две команды A и B так, чтобы величина |max(A)−min(B)| была как можно меньше, где max(A) — максимальная сила спортсмена из команды A, а min(B) — минимальная сила спортсмена из команды B.

Например, если n=5 и силы спортсменов равны s=[3,1,2,6,4], то одно из возможных разделений на команды имеет вид:

первая команда: A=[1,2,4],
вторая команда: B=[3,6].
В этом случае величина |max(A)−min(B)| будет равна |4−3|=1. Этот пример иллюстрирует один из способов оптимального разбиения на две команды.

Выведите минимальное значение |max(A)−min(B)|.

Код

#include <bits/stdc++.h>
using namespace std;

int main() {
	int test;
	cin >> test;

	for (int tt = 0; tt < test; tt++) {
		int n;
		cin >> n;

		vector<int> a(n);

		for (int &x : a) {
			cin >> x;
		}

		sort(a.begin(), a.end());

		int result = a[n - 1] - a[0];

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				result = min(result, a[j] - a[i]);
			}
		}

		cout << result << endl;
	}

	return 0;
}

         

Firdavskhon Photo Автор: Firdavskhon


Найдем двух спортсменов с номерами a и b (сила a не больше силы b), модуль разности сил которых минимален. Очевидно, что мы не можем получить ответ, меньше чем эта величина. Покажем, как получить разбиение ровно с таким ответом.

Отсортируем всех спортсменов по силе. Тогда наши два спортсмена будут стоять в соседних позициях (если бы это было не так, то мы бы могли уменьшить ответ). Тогда отправим всех спортсменов которые стоят на позиции не позже, чем a в первую команду, а остальных во вторую. Мы получили разбиение на команды, в котором спортсмен с номером a самый сильный в первой команде, а спортсмен с номером b самый слабый во второй.


Комментарии

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