Codeforces Round 896 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие состоит в том, что в этой версии каждый должен дать конфеты не более чем одному человеку и получить конфеты не более чем от одного человека. Обратите внимание, что посылка не может пройти обе версии задачи одновременно. Вы можете делать взломы, только если обе версии задачи решены.
После экзамена Daniel и его друзья собираются устроить вечеринку. Все придут с конфетами.
На вечеринке будут присутствовать $$$n$$$ человек. Изначально у $$$i$$$-го человека есть $$$a_i$$$ конфет. Во время вечеринки они будут обмениваться конфетами. Для этого они выстроятся в произвольном порядке и каждый из них сделает следующее не более одного раза:
Daniel любит справедливость, поэтому он будет счастлив тогда и только тогда, когда каждый получит конфеты от не более чем одного человека. В то же время его друг Tom любит среднее, поэтому он будет счастлив тогда и только тогда, когда у всех людей будет одинаковое количество конфет после всех обменов.
Определите, существует ли способ обменяться конфетами так, чтобы Daniel и Tom были счастливы после обменов.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество человек на вечеринке.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — количество конфет у каждого человека.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите «Yes» (без кавычек), если существует способ обменяться конфетами так, чтобы Daniel и Tom были счастливы, и выведите «No» (без кавычек) в противном случае.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ.
632 4 351 2 3 4 561 4 7 1 5 4220092043 20092043129 9 8 2 4 4 3 5 1 1 1 162 12 7 16 11 12
Yes Yes No Yes No Yes
В первом наборе входных данных второй человек даёт $$$1$$$ конфету первому человеку, поэтому у всех людей есть по $$$3$$$ конфеты.
Во втором наборе входных данных четвёртый человек даёт $$$1$$$ конфету второму человеку, пятый человек даёт $$$2$$$ конфеты первому человеку, третий человек ничего не делает. После всех обменов у каждого есть по $$$3$$$ конфеты.
В третьем наборе входных данных невозможно сделать так, чтобы у всех людей было одинаковое количество конфет.
В четвёртом наборе входных данных двум людям не нужно ничего делать.
Название |
---|