Блог пользователя kb.

Подскажите идею решения (подробности внутри)
Автор kb., 14 лет назад, По-русски
Здравствуйте! Устрашенный заявлениями подполковника Ferlon'а о "вытирании ног об новичков", я все таки решился создать эту тему. Надеюсь, что еще остались люди, которые считают помощь новичкам нормальным поступком и не думают, что я скоро раскачаюсь и всех "одержу" :D .
Ну это было вступление. Теперь к вопросу: решая эту задачу, я свел ее к следующей проблеме: есть A групп по X человек и B групп по (X+1) человек. Как оптимально разбить эти группы на два больших множества, так чтобы разность между количествами человек в них была минимальной? Как мне кажется, кроме перебора существует и более разумное решение, но его я найти не смог. Придумал только разве что (X * (X+1)) = ((X+1) * X), а значит можно часть групп распределить равномерно, а дальше все равно получается перебор, и я даже не уверен, что это правильно.
Подскажите, пожалуйста, правильную идею!
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
(я не читал исходную задачу, решаю переформулированную)
Нужно выбрать множество групп, чтобы сумма в нем была как можно ближе к T=(AX+B(X+1))/2 (второе множество - все остальные группы). Переберем количество групп в этом множестве, пусть их k. Пусть из них p групп размера X+1 (остальные k-p размера X), p<=k, p<=B, k-p<=A. Людей в этом множестве p*(X+1)+(k-p)*X=k*X+p. Значит оптимальное p=T-k*X, но столько может не быть, так что нужно взять как можно более близкое из возможных. Окончательно получаем p=min(min(k,B),max(k-a,T-k*X)), считаем |(k*X+p)-T|, берем максимум по всем k, получаем ответ. Домашнее задание - придумать, что делать, если T не целое :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Если А и Б оба четные, то легко -- в первую группу по половине каждых, и во вторую.

Если оба нечетные -- то тоже легко, в одну группу на одного больше из А, во вторую на одного больше из Б, разница будет 1. Меньше нельзя.

Если ни то ни другое (то есть А + Б нечетное), но А больше равно Х+1, а Б больше равно Х, то кидаем в первую группу Х+1 из А, во вторую Х из Б, затем А+Б становится четным, решаем для одного из случаев сверху.

Наконец, в последних двух случаях кажется, что не остается ничего, кроме как кинуть в первую группу все из А, во вторую все из Б, а затем переносить из большей группы в меньшую, пока в первой группе не останется ровно на одного человека больше, чем во второй (А+Б нечетное, как мы помним).

 

→ Ответить