User 13882072 Ответов: 2

Как мне решить этот код за время, равное 1,5 сек

входной формат:
Первая строка содержит целое число N, обозначающее количество контейнеров.
Вторая строка содержит целое число M, обозначающее количество дней.
Каждая из следующих M строк состоит из двух целых чисел l и r, разделенных пробелами.
Затем следует целое число Q, обозначающее количество запросов.
Каждая из следующих Q строк содержит одно целое число K.

выходной формат:
Для каждого запроса выведите результат в новой строке.

Ограничения:
1 <= N <= 100000
1 <= M <= 1000
1 <= l <= r <= N
1 <= Q <= 100000
1 <= K <= N

Что я уже пробовал:

def add(a,b):
    for i in xrange(a-1,b):
        box[i]+=1
def count(k):
    if box.count(k)!=0:
        box.index(k)
        return len(box)-box.index(k)
    else:
        return 0
from sys import stdin,stdout
box=[0]*int(stdin.readline())
for i in xrange(int(stdin.readline())):
    a,b = stdin.readline().split()
    add(int(a),int(b))
box.sort()
for i in xrange(int(stdin.readline())):
    print count(int(stdin.readline()))

Mehdi Gholam

Сначала попробуйте определить свой вопрос так, чтобы он был понятен (более 1,5 секунды).

[no name]

Ограничение по времени превышается когда я запускаю этот код я хочу чтобы этот код выполнялся за 1,5 секунды

[no name]

Это и есть постановка вопроса
Аджай очень любит шоколад. У него есть N контейнеров, пронумерованных от 1 до N. каждый день он выбирал два индекса [l,r] и добавлял по 1 шоколаду в каждую коробку, начиная с l до r (оба включительно).Он повторяет одно и то же действие в течение M дней.

После м дней, он попросил своего знакомого Накул Q запросов. Каждый запрос можно описать следующим образом: сколько контейнеров имеет по крайней мере K шоколадных конфет.
Помогите Накулу ответить на эти вопросы.

2 Ответов

Рейтинг:
2

Patrice T

Этот текст типичен для сайта "programming challenge", но вы забыли ту часть, в которой говорится, что такое контекст и цель, и вы не предоставляете никакой ссылки на исходную проблему.
Поэтому мы не знаем, что делает ваш код и почему.

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

Тот факт, что ваш код не решает проблему в срок, просто говорит о том, что ваш код недостаточно умен. Вам нужно оттачивать свои навыки в структурах данных и алгоритмах.

Это домашнее задание для себя, и весь интерес заключается в том, чтобы знать, можете ли вы решить самостоятельно или нет.

Рейтинг:
1

OriginalGriff

Это вызов, а значит, и домашнее задание.
И мы не делаем домашнее задание: оно задано не просто так. Она существует для того, чтобы вы думали о том, что вам сказали, и пытались понять это. Он также существует для того, чтобы ваш наставник мог определить области, в которых вы слабы, и сосредоточить больше внимания на корректирующих действиях.

Попробуйте сами, возможно, вы обнаружите, что это не так сложно, как вы думаете!

Если вы столкнетесь с конкретной проблемой, то, пожалуйста, спросите об этом, и мы сделаем все возможное, чтобы помочь. Но мы не собираемся делать все это для вас!