Как можно оптимизировать задачу?
Носки
Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Вася, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках. Конец носка также накрывает точку стола, в которой он находится.
Входные данные
В первой строке заданы L,N,M(1≤L≤10000,1≤N≤10000,1≤M≤100000).
Далее идут N пар чисел l≤r от 1 до L — левые и правые концы носков, каждая в отдельной строке.
Затем идут M чисел от 1 до L — интересующие Васю точки, каждое в отдельной строке.
Все числа целые.
Выходные данные
Выведите M чисел — толщину носкового покрытия в каждой точке.
Примеры
Ввод
31 12 4
19 20
1 3
9 26
8 31
15 26
15 20
5 20
17 27
21 23
2 24
10 19
1 27
15
23
28
Вывод 8
7
1
7
С задачей я разобрался , но как придумать эффективное решение? Данный код не проходит по времени
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int l;
cin >> l;
int n;
cin >> n;
int m;
cin >> m;
vector<int> a (n);
vector<int> b(n);
vector<int> c(m);
for(int i = 0 ; i < n;i++) {
cin >> a[i];
cin >> b[i];
}
for(int i = 0 ; i < m;i++) {
cin >> c[i];
}
for(int j=0;j<m;j++) {
int ans = 0;
for(int i = 0 ; i < n;i++) {
if (a[i] <= c[j] && c[j] <= b[i]) {
ans++;
}
}
cout << ans << endl;
}
}
Ответы (1 шт):
Создайте общий массив/вектор, содержащий пары (координата; признак -1/0/+1). Признак -1 соответствует концу носка, +1 - началу носка, 0 - "интересующая точка".
Отсортируйте массив по координате. При равенстве координат +1 идёт раньше (чтобы учесть Конец носка также накрывает точку стола, в которой он находится)
Вначале покрытие = 0. Пройдите по массиву, добавляя значение признака к покрытию. Если признак=0 - выведите текущее значение покрытия.
Пример на Python
lf = [2, 4, 6, 7] # левые концы
rt = [8, 7, 7, 9] # правые концы
chk = [1, 5, 6, 7, 9] # точки проверки
pt = []
for x in lf:
pt.append((x, 1))
for x in rt:
pt.append((x, -1))
for x in chk:
pt.append((x, 0))
pt.sort(key=lambda point: (point[0], -point[1]))
print(pt)
coverage = 0
for x in pt:
if x[1] == 0:
print(x[0], coverage)
coverage += x[1]
[(1, 0), (2, 1), (4, 1), (5, 0), (6, 1), (6, 0),
(7, 1), (7, 0), (7, -1), (7, -1), (8, -1), (9, 0), (9, -1)]
1 0
5 2
6 3
7 4
9 1