Распределить запросы между серверами

@Xdigital · Регистрация: 08.11.2024

Студворк — интернет-сервис помощи студентам

Есть серверный кластер, обрабатывающий запросы от пользователей. Каждый запрос имеет определенное время обработки, и для оптимальной работы кластера нужно равномерно распределить запросы между серверами, чтобы минимизировать максимальное время ожидания.
Условия:
1. У вас есть k серверов, работающих параллельно, и каждый запрос выполняется на одном сервере.
2. Поступило n запросов, каждый из которых имеет время обработки ti.
3. Требуется распределить запросы между серверами так, чтобы минимизировать максимальное время обработки среди серверов.
Входные данные:
Количество запросов n и количество серверов k (k≤n≤1000).
Список запросов t=[t1,t2,...,tn], где 1≤ti≤1000- время обработки i-го запроса. Выходные данные:
Минимальное возможное время, в течение которого все запросы будут обработаны (наибольшее время обработки одного сервера).
Пример:
Входные данные: 6 3 2 3 7 1 6 5
Выходные данные: 8
Объяснение: Запросы можно распределить между серверами так: :
Сервер 1 обрабатывает запросы со временем обработки 7+1=8
Сервер 2 обрабатывает запросы со временем обработки 6+2=8
Сервер 3 обрабатывает запросы со временем обработки 5+3=8
Максимальное время обработки - 8, и это минимально возможный результат.

@Red white socks · 08.11.2024, 10:27

Проблема в чем? Задача для детсада.

Отсортируйте запросы по убыванию времени и обрабатывайте их первым освободившимся сервером

@Xdigital · 09.11.2024, 18:59 **[ТС]**

Red white socks, ну я сделал так, только не знаю правильно или нет, ну если брать пример то работает

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def distribute_tasks(tasks, servers):
 
    tasks.sort(reverse=True)
    server_loads = [0] * servers
 
    for task in tasks:
        min_load_index = server_loads.index(min(server_loads))
        server_loads[min_load_index] += task
 
    return max(server_loads)
 
if __name__ == "__main__":
 
    input_line = input()
    n, k = map(int, input_line.split())
 
    
    if not (1 <= k <= n <= 1000):
        print("")
        exit()
 
    
    tasks_str = input()
    tasks = list(map(int, tasks_str.split()))
 
   
    result = distribute_tasks(tasks, k)
    print(result)

@Red white socks · 12.11.2024, 23:21

Xdigital, спасибо за отклик на мой провокационный пост. Извините за него.
Xdigital, данная задача - разновидность NP-полной задачи о разбиении множества чисел.
Указанный алгоритм - одна из эвристик, дающих приближенное решение.
Для 1000 запросов найти точное решение мне не представляется возможным. Если расскажете источник происхождения задачи, возможно, что-то удастся придумать.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@Xdigital 0 / 0 / 0 Регистрация: 08.11.2024 Сообщений: 3

	Распределить запросы между серверами 08.11.2024, 09:59. Показов 782. Ответов 3 Метки нет (Все метки) Есть серверный кластер, обрабатывающий запросы от пользователей. Каждый запрос имеет определенное время обработки, и для оптимальной работы кластера нужно равномерно распределить запросы между серверами, чтобы минимизировать максимальное время ожидания. Условия: 1. У вас есть k серверов, работающих параллельно, и каждый запрос выполняется на одном сервере. 2. Поступило n запросов, каждый из которых имеет время обработки ti. 3. Требуется распределить запросы между серверами так, чтобы минимизировать максимальное время обработки среди серверов. Входные данные: Количество запросов n и количество серверов k (k≤n≤1000). Список запросов t=[t1,t2,...,tn], где 1≤ti≤1000- время обработки i-го запроса. Выходные данные: Минимальное возможное время, в течение которого все запросы будут обработаны (наибольшее время обработки одного сервера). Пример: Входные данные: 6 3 2 3 7 1 6 5 Выходные данные: 8 Объяснение: Запросы можно распределить между серверами так: : Сервер 1 обрабатывает запросы со временем обработки 7+1=8 Сервер 2 обрабатывает запросы со временем обработки 6+2=8 Сервер 3 обрабатывает запросы со временем обработки 5+3=8 Максимальное время обработки - 8, и это минимально возможный результат. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	08.11.2024, 10:27
	Проблема в чем? Задача для детсада. Отсортируйте запросы по убыванию времени и обрабатывайте их первым освободившимся сервером 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.11.2024, 23:21
	Xdigital, спасибо за отклик на мой провокационный пост. Извините за него. Xdigital, данная задача - разновидность NP-полной задачи о разбиении множества чисел. Указанный алгоритм - одна из эвристик, дающих приближенное решение. Для 1000 запросов найти точное решение мне не представляется возможным. Если расскажете источник происхождения задачи, возможно, что-то удастся придумать. 0