Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Задача про конференцію з обміну досвідом
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Уявіть собі, що вам випала честь відповідати за розселення гостей на конференції з обміну досвідом. Кожен гість представляє одну галузь знань, і кожну галузь можуть представляти декілька гостей. Всі гості жадають отримати якомога більше знань з інших галузей. Ваше завдання поселити гостей так, щоб гості з однієї галузі знань не проживали поруч. Наприклад,
Вхід: aaabc
Вихід: abaca
Вхід: aa
Вихід: Немає розв'язку
0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.
І що складного? селити на різних поверхах.
0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.
Мені знов соромно за себе, я хотів використовувати купу, і на кожному кроці вибирати елемент з того, якого найбільше залишилось.
0. Перевіряємо, чи гостей якоїсь галузі не більше, ніж половина. Якщо більше - немає розв'язку.
1. Сортуємо гостей за кількістю (щоб виходило cccaab). Можна скористатися сортуванням підрахунком, це тут оптимально.
2. Розставляємо першу половину на парні місця, решту на непарні.
Оскільки сортування підрахунком складається з двох фаз, першу можна сумістити з п.0, другу - з п. 2. Тобто просто модифікуємо сортування підрахунком і все.
По духу задачі краще було б модифікувати другий пункт:
2. Розставляємо першу третину на місця, що діляться без остачі на 3, другу - на місця, що дають остачу 1, а третю - на місця, що дають остачу 2.
Учасники краще поставляться до схеми abcabcabcabc, ніж до ababacacbcbc.
Але це якщо змінити завдання на "задовольніть найбільше учасників".
Але це за умови, що це можливо. Інакше доведеться шукати спершу розміщення для елементів a (частину - через 2, частину - через 1), потім - для елементів b...
Я не можу зрозуміти поки що, про який випадок ви говорите. Якщо найбільша група більша за n/3 + 1, то розміщення з унікальними сусідами немає, а в іншому випадку алгоритм працює. Чи ні?
Розміщення немає, але може бути наближення, краще за перший алгоритм. Скажімо, для набору aaaabbbcc варіант abcabcaba виглядає привабливішим за ababacacb.
А якщо крісла у конференцзалі стоять не в 1 ряд а є багатовимірним масивом? Припустимо що в один ряд по 4 крісла і тоді ababacacbcbc перетвориться в:
abab
acac
bcbc
Тепер виходить що а сидить ззаду за a, с за с і т.д.
Вийшло таке..
$input = 'aaaabbcccff';
//переторюємо рядок в масив та в новий масив типу
// 'буква'=>'її кількість'
$acv = array_count_values(str_split($input));
//сортуємо його по кількості від більшого до меншого
arsort($acv);
//новий масив
$arr = [];
//перебираємо масив acv за ключем і значенням
foreach($acv as $key=>$value)
//пишемо в масив вкладені масиви, які
//складаються з кількості символів типу 3 - (a,a,a)
$arr[] = str_split(str_repeat($key, $value));
//далі з кожного масиву беремо по черзі один елемент
$out = null;
for($i=0; $i<count($arr[0]); $i++)
for($j=0; $j<count($arr); $j++)
$out.= isset($arr[$j][$i]) ? $arr[$j][$i] : null;
echo 'Input: '.$input.PHP_EOL.'Out: '.$out;Результат: http://ideone.com/7PU9VB
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися