1

Всем добрый день. Решаю задачу на питоне но не знаю в чем ошибка. Вот сама задача:

Задача 1.5. Обработка запросов [Реализация; cтруктуры данных; два указателя; двоичный поиск] Алиса проектирует вычислительную систему, предназначенную для обработки большого числа однотипных запросов. Проектируемая система будет содержать некоторое количество одинаковых процессоров. В каждый момент времени каждый процессор может быть либо свободен, либо занят обработкой ровно одного запроса. Продолжительность обработки является одинаковой для всех запросов и составляет s миллисекунд. Система должна работать в режиме реального времени, то есть каждый поступивший запрос должен незамедлительно передаваться на обработку любому свободному процессору.

Алиса хочет понять, сколько процессоров должна содержать вычислительная система. Для этого она собрала статистические данные о работе подобных систем в прошлом. Каждый набор данных содержит n чисел t1, t2,…,tn, где ti — момент поступления запроса с номером i. Числа в наборе могут повторяться, однако, они упорядочены по не убыванию. Если некоторый процессор приступил к обработке некоторого запроса в момент ti, то в момент t i +s он сможет начать обрабатывать новый запрос.

Набор может содержать достаточно большой объем данных, поэтому от вас требуется написать программу, которая определит, какое минимальное число процессоров должно быть в вычислительной системе, чтобы все запросы были обработаны в момент их поступления.

Формат входных данных На вход в первой строке подается два натуральных числа n и s — количество запросов и время обработки одного запроса, 1≤n≤200000, 1≤s≤10⁹ . Во второй строке записаны целые неотрицательные числа t1,t2,…,tn, задающие моменты времени поступления запросов, 0 ≤ t1 ≤ t2 ≤ ⋯≤ tn ≤ 10⁹ .

Формат выходных данных Вывести одно число — минимальное количество процессоров, которое позволит обработать все запросы в момент их поступления.

Методика проверки Программа проверяется на 30 тестах. Прохождение каждого теста оценивается в 1 балл. Тесты из условия задачи при проверке не используются. Ниже в таблице приведены возможные тестовые случаи. введите сюда описание изображения

Sample Input 1: 9 30 90 90 90 120 120 120 120 200 200

Sample Output 1: 4


Sample Input 2: 10 30 0 25 110 125 125 130 140 140 140 155

Sample Output 2: 6

Пояснение к примерам Первый пример соответствует первому тестовому случаю. В момент времени 120 приходит сразу четыре запроса, для обработки которых потребуется четыре процессора.

Расписание выполнения запросов во втором примере можно представить в следующей таблице. введите сюда описание изображения Пять процессоров для своевременной обработки всех запросов будет уже недостаточно.

А вот мой код:

def min_processors(n, s, t):
    i_s = 0
    i_f = 1
    cnt = 1

    while i_s < n - 1:
        if t[i_f] + s <= t[i_s]:
            cnt -= 1
            i_f += 1
        else:
            cnt += 1
            i_s += 1

    return cnt

n, s = map(int, input().split())
t = list(map(int, input().split()))

result = min_processors(n, s, t)
print(result)

1
  • Если вопрос касается разработки алгоритма, указывайте соотв. метку. А версия питона в этом случае не играет особой роли (правда, не все так думают)
    – MBo
    9 сен в 15:15

2 ответа 2

2

Моменты старта у вас упорядочены и время обработки постоянное - это хорошо, задача упрощается, её можно решить за линейное время.

Послушаемcя директивы два указателя

Начнём работу после старта первого интервала. Запускаете два индекса i_s = 1 для старта и i_f = 0 для окончания интервалов. Заводите счётчик активных интервалов cnt=1

В цикле проверяете - что идёт раньше - t[i_f]+s или t[i_s]. При равенстве сначала обрабатываете концы - это достигается просто использованием <= - if t[i_f]+s <= t[i_s]

При обработке конца делаете cnt -= 1 и i_f +=1

При обработке начала делаете cnt += 1 и i_s +=1

Максимальное достигнутое значение cnt - нужный результат.

def min_processors(n, s, t):
    i_f = 0
    i_s = 1
    cnt = 1
    max_cnt = 1

    while i_s < n:
        if t[i_f] + s <= t[i_s]:
            cnt -= 1
            i_f += 1
        else:
            cnt += 1
            max_cnt = max(max_cnt, cnt)
            i_s += 1

    return max_cnt

n, s = 9, 30
#t = list(map(int, "90 90 90 120 120 120 120 200 200".split()))
n, s = 10, 30
t = list(map(int, "0 25 110 125 125 130 140 140 140 155".split()))

result = min_processors(n, s, t)
print(result)
13
  • извини, но можешь засунуть в программу мою?
    – Nymos
    9 сен в 14:26
  • да и используя Sample Input 1: 9 30 90 90 90 120 120 120 120 200 200, выдает 2
    – Nymos
    9 сен в 14:35
  • Были перепутаны начальные значения i_f, i_s (видимо, из-за этого условие цикла неверное). Не выполнялось нахождение максимума cnt
    – MBo
    9 сен в 14:54
  • программа вообще не работает твоя
    – Nymos
    9 сен в 14:56
  • На тесте даёт 4
    – MBo
    9 сен в 14:57
0

Ваш код не учитывает окончание первого задания (индекс i_f начинается с единицы) и начало последнего (индекс i_s заканчивается на n - 2). Для n = 3, s = 1, t = [0, 10, 20] вы возвращаете 3, хотя задания короткие и одного процессора должно хватить.

Решим задачу красиво. Это, конечно, заметание. Половина событий - времена начал обработки запросов:

es = ((ti, 1) for ti in t)

Вторая половина - времена окончаний обработки запросов:

ef = ((ti + s, -1) for ti in t)

Их нужно собрать в общую последовательность. heapq.merge:

e = heapq.merge(es, ef)

После смешивания метки времени не нужны. Оставим только флажки:

e = (c for _ , c in e)

Чтобы найти нужное число процессоров в каждый момент времени, сосчитаем накопительные суммы. itertools.accumulate:

a = itertools.accumulate(e)

Нам нужен максимум:

max(a)

Всё вместе:

import heapq
import itertools

_, s = map(int, input().split())
t = tuple(map(int, input().split()))
print(max(itertools.accumulate(
    c
    for _ , c in heapq.merge(
        ((ti    ,  1) for ti in t),
        ((ti + s, -1) for ti in t)
    )
)))

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.