Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/15: Рейтинг темы: голосов - 15, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7

Задача на нахождение максимального кол-ва пересечений отрезков в точке (оптимизировать алгоритм)

27.08.2020, 12:40. Показов 3311. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день!
В общем и целом есть задача и звучит она так:
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
На прямoй располагаeтся 1 ≤ N ≤ 10000 тoчек с целочислeнными кooрдинатами –10^9 ≤ Vi ≤ 10^9. Кaждой из тoчек рaзрешается сдeлать рoвно однo движениe (тaнцевальное пa) в любoм напpавлении на рaсстояние нe большe 0 ≤ L ≤ 10^8 и остановитьcя нa дрyгой пoзиции. Какоe минимaльное кoличество тoчек мoжет oстаться нa прямoй пoсле oкончания тaнца (всe точки послe танцa, oказывающиеся на oдной пoзиции, сливaются в oдну)?
Формат входных данных:
L N
V1 V2 … VN
Формат выходных данных:
MinimalNumberOfPoints
Примеры:
Входные данныеВыходные данные
10 5 30 3 14 19 212
Задача взята из: https://www.babichev.org/books/AlgoBook.pdf (Страница 85) (Находится в общем доступе)
Моё видение задачи

Как я понял, задача не о точках, а об отрезках
То есть точка может сдвигаться от своей позиции на длину L влево или вправо
Соответственно, она образует отрезок на прямой
Вся суть задачи заключается в том, чтобы найти те точки, которые вмещают максимальное кол-во отрезков, сами при этом не двигаясь
Например, для тестовых входных данных это точки 3(до неё никто не дотянется) и 21(к ней дотянутся 30, 14 и 19)
Соответственно, ответ 2


Я сделал, так сказать, в лоб. Вот что получилось:
Мой вариант
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <map>
#include <algorithm>
#include <fstream>
 
using input_stream = std::istream;
 
// Проверяет, являются ли 2 точки досигаемыми друг для друга
// при танцевальном па одной из них
bool is_adjacent(int n1, int n2, int turn_length)
{
    auto minmax = std::minmax(n1, n2);
    return (minmax.first + turn_length) >= minmax.second;
}
 
void process_reading(input_stream & ios)
{
    int turn_length;
    int n;
    std::map<int, int> elems;
 
    ios >> turn_length >> n;
    for (int i = 0, tmp; i < n; ++i)
    {
        ios >> tmp;
 
        // Находим все смежные с этим элементы
        // Так же добавляем уже существующим +1
        int adj_elems = 0;
        for (auto & [k, v] : elems)
        {
            if (is_adjacent(tmp, k, turn_length))
            {
                ++adj_elems;
                ++v;
            }
        }
        elems[tmp] = adj_elems;
    }
    
    int result = 0;
    int adj_left = 0;
    int adj_last = 0;
 
    // Идём по всем элементам
    for (const auto & [k, v] : elems)
    {
        // Если у элемента 0 соседей, то он не может никуда сдвинуться
        // и к нему никто сдвинуться не может
        // Следовательно, он единственный на этом отрезке и не может ни с кем "спариться"
        if (v == 0)
        {
            adj_last = 0;
            ++result;
            continue;
        }
 
        --adj_left;
        
        // Проверяем, если кол-во соседей текущего отрезка больше,
        // чем кол-во соседей взятого раньше отрезка
        // Если больше, то мы берём его и вычитаем из его соседей уже прошедших соседей,
        // чтобы получить число оставшихся впереди соседей
        // Если равно, то для нас не имеет значения, возьмём мы предыдущий отрезок или этот
        if (v > adj_last)
        {
            adj_left = v - adj_last;
            adj_last = v;
            continue;
        }
 
        // Когда мы прошли всех соседей, то это значит, что больше мы вместить не можем
        // Прибавляем результат и обнуляем последний отрезок, чтобы взять следующий
        if (adj_left == 0)
        {
            ++result;
            adj_last = 0;
        }
    }
 
    // В итоге несколько соседей могут остаться
    // Потому что некоторые соседи могут остаться на предыдущем отрезке
    if (adj_left > 0)
        ++result;
 
    std::cout << "result: " << result << std::endl;
}
 
int main(int argc, char * argv[])
{
    if (argc <= 1)
    {
        process_reading(std::cin);
        return EXIT_SUCCESS;
    }
 
    std::ifstream ifs{argv[1]};
    if (ifs.is_open() == false)
    {
        std::cerr << "Can't open file: " << argv[1] << "\n";
        return EXIT_FAILURE;
    }
 
    process_reading(ifs);
}


Но он явно проигрывает по скорости исполнения, потому что при шаге в 100000 и кол-ве элементов всего лишь в 35000(от 1 до 35000)
Программа на моём процессоре исполняется 4.5 секунды с оптимизациями компилятора, что явно намекает на плохой алгоритм
Помогите исправить алгоритм так, чтобы он проходил тест
Или подскажите, как надо такую задачу решать
Хотя бы направление дайте
Я понимаю, что в книге эта задача из главы "Жадные алгоритмы", но всё равно как-то для меня слишком это сложно оказалось
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
27.08.2020, 12:40
Ответы с готовыми решениями:

Задача на нахождение кол-ва дней до нового года по месяцу и дню
Вводится месяц и день месяца, а выводится кол-во дней до НГ. При некорректном вводе выводится -1.Решать без массивов. Я вроде-бы...

Алгоритм Форда-Фалкерсона. Нахождение максимального потока сети
В одном из городов имеется производство обуви на экспорт. Вся обувь отправляется диллерам морским путем через один и тот же порт. Для...

Графы. Алгоритм DFS. Нахождение максимального количества независимых рёбер
Добрый день, уважаемые Гуру. Хотел бы попросить помощи. Задача - найти максимальное количество независимых рёбер в связном графе, не...

11
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
27.08.2020, 13:10
Может я не так понял, но я бы нашел точку с минимальной(min) и максимальной(max) координатой.
Если существует отрезок [min + L, max - L](т.е. отрезки [min, min + L] и [max - L, max] не пересекаются), то если в этом отрезке существует хотя бы одна точка - ответ 3.
Иначе, если длина отрезка [min, max] > L - ответ 2.
Иначе ответ 1.

Добавлено через 17 минут
Извиняюсь, невнимательно прочитал. Не увидел что L тоже задаётся как входной параметр.
Тогда предварительная сортировка массива. Дальше принцип тот же, только в первом случае прибавляем к результату 2, исключаем эти два крайних отрезка и повторяем проверки.
0
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
27.08.2020, 15:34  [ТС]
Цитата Сообщение от zayats80888 Посмотреть сообщение
Дальше принцип тот же
Немного не понял
Какими тогда при этом подходе будут min и max?
Первый и последний элемент сортированного массива или это должен быть какой-то локальный минимум/максимум?
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
27.08.2020, 16:49
Цитата Сообщение от Warhan Посмотреть сообщение
Немного не понял
Попробуйте так, я особо не тестил, но вроде работает:
C++
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
29
30
31
32
#include <algorithm>
template <class RandomIt, class T>
size_t foo(RandomIt first, RandomIt last, const T& length)
{
    size_t result{};
 
    std::sort(first, last);
 
    for (; first != last;)
    {
        T min = *first;
        T max = *(last - 1);
        
        first = std::upper_bound(first, last, min + length) - 1;
        last = std::lower_bound(first, last, max - length);
 
        if (first != last)
        {
            result += 2;
            T min = *first;
            T max = *last;
 
            first = std::upper_bound(first, last, min + length);
            last = std::lower_bound(first, last, max - length);
        }
        else
        {
            result += 1;
        }
    }
    return result;
}
1
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
27.08.2020, 17:00
Сначала, конечно, отсортировать. Желательно ещё и одинаковые удалить (другая точка с той же координатой будет вести себя как первая).

Далее можно представить ситуацию, когда у нас есть группа точек в точке a, одна точка в точке b, и ещё группа точек в точке c. По отдельности эти 3 группы дадут к ответу +3. Если мы точку из a или из c двинем в b, то ответ тоже +3 (т.к мы одинаковые удалили, то из группы может двигаться не более одной(которая сразу стояла на этой координате)). А если мы b двинем куда-то в a или c, то ответ +2.

Я этим хотел сказать, что нам все равно куда будет ходить точка - вправо/влево, главное, чтобы она попала в одну из групп точек. То есть, полагаю, алгоритм будет жадным : Первая точка сразу вправо ко второй(если не может дойти, то на L вправо). Следующие точки будут просто стремится к объединению с той, которая слева. Иначе, если не могут дойти до левой, то вправо к i+1 точке (если не может дойти, то на L вправо).
Не очень уверен вообще в жадных алгоритмах, но вроде бы должно работать. Иначе, хотелось бы увидеть контрпример.
1
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
27.08.2020, 17:15
C++
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
29
#include <iostream>
#include <vector>
 
int main()
{
    int l, n;
    std::cin >> l >> n;
 
    std::vector<std::pair<int, char>> vec(n * 2);
 
    for (short i{}, s; i < n; ++i) {
        std::cin >> s;
        vec[i * 2] = { s - l, 'l' };
        vec[i * 2 + 1] = { s + l, 'r' };
    }
 
    std::sort(vec.begin(), vec.end(), [](auto lhs, auto rhs) { return lhs.first < rhs.first; });
 
    size_t cnt{}, max_overlap{};
 
    for (auto& it : vec) {
        if (it.second == 'l') max_overlap = std::max(++cnt, max_overlap);
        else --cnt;
    }
 
    std::cout << n - max_overlap + 1;
 
    return 0;
}
2
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
27.08.2020, 17:37
nalbe666, то ли я не понял, то ли ваш алгоритм не так подсчитывает.
Для 0 3 0 0 0 у вас выводит 3, хотя вроде должно вывести 1.
Для 1 3 1 2 3 у вас выводит 2, хотя вроде должно вывести 1.

Добавлено через 10 минут
Если подправить предикат сортировки так, то вроде правильно отрабатывает
C++
1
2
// это при условии что 'l' < 'r'
[](auto lhs, auto rhs) { return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second); }
1
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
27.08.2020, 17:45
zayats80888, да, спасибо, не проверил до конца.
0
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
27.08.2020, 21:15  [ТС]
Цитата Сообщение от zayats80888 Посмотреть сообщение
Попробуйте так, я особо не тестил, но вроде работает
Спасибо!
Работает правильно на всех наборах, которые я пробовал
А можете подсказать, что можно почитать, чтобы такие алгоритмы научиться писать?
Книги какие-нибудь
Может, это какой-то специфический случай более общей задачи, у которой есть какие-то алгоритмы решения?
0
 Аватар для Annemesski
2674 / 1336 / 480
Регистрация: 08.11.2016
Сообщений: 3,692
28.08.2020, 11:48
Цитата Сообщение от Warhan Посмотреть сообщение
Книги какие-нибудь
Литература С++

Роберт Седжвик - "Алгоритмы на C++".

Факултативно:
Герб Саттер - "Решение сложных задач на C++" и "Новые сложные задачи на C++".

Перед началом занятий по этим книгам рекомендую к изучению:
Эндрю Кениг, Барбара Му "Эффективное программирование на C++".
0
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
09.09.2020, 20:39  [ТС]
zayats80888, всё же ваш алгоритм работает неправильно
Потому что он предполагает, что точка, к которой происходит движение, не двигается
Это была ошибка в моём алгоритме и вы её унаследовали почему-то
В задаче не говорится об этом
В итоге я разобрался сам и вот верный итоговый вариант:
C++
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
void process_reading3(input_stream & ios)
{
    int turn_length;
    int n;
    std::vector<int> elems;
 
    ios >> turn_length >> n;
    elems.resize(n);
    for (int i = 0; i < n; ++i)
    {
        ios >> elems[i];
    }
 
    auto first = elems.begin();
    auto last = elems.end();
    int result{};
 
    std::sort(first, last);
    for (; first != last;)
    {
        ++result;
        first = std::upper_bound(first, last, *first + (turn_length * 2));
    }
    std::cout << "result: " << result << std::endl;
}
Всё оказалось легче, чем я думал

Добавлено через 7 минут
Цитата Сообщение от zayats80888
C++
1
[](auto lhs, auto rhs) { return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
C++
1
[] (auto lhs, auto rhs) { return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second); }
Или даже
C++
1
[] (auto lhs, auto rhs) { return lhs < rhs; }
0
 Аватар для zayats80888
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
09.09.2020, 20:57
Цитата Сообщение от Warhan Посмотреть сообщение
Это была ошибка в моём алгоритме и вы её унаследовали почему-то
Мне просто показалось, что
Цитата Сообщение от Warhan Посмотреть сообщение
остановитьcя нa дрyгой пoзиции
означает остановится на позиции другой точки. Но если это вообще любая позиция на числовой оси, то да - всё гораздо проще .
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.09.2020, 20:57
Помогаю со студенческими работами здесь

Нахождение пересечений объектов типа geometry
Доброго времени суток! Суть вопроса - есть БД, в которой хранятся 2 таблицы с полем geometry, в одной хранится набор полигонов (земельные...

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

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

Алгоритм обработки матрицы: Нахождение максимального элемента матрицы и его номера.
Алгоритм обработки матрицы: Нахождение максимального элемента матрицы и его номера.

Дано множество отрезков; найти отрезок, середина которого ближе всего к заданной точке
Дано множество отрезков. Среди отрезков, длина которых больше D, найти отрезок, середина которого ближе всего к точке (15, 15).


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru