Сортировки и жадности

Пятница, 16 сентября 2016
Таймс, 4 этаж

Описание

Для понимания происходящего полезно знать содержимое части 3.1.Жадность.Введение из онлайн-курса.

  • Сортировка на C++, Java.

  • Задачи про точки и отрезки на прямой

    • Максимальное число непересекающихся отрезков
    • Найти длину объединения отрезков
    • Найти точку, покрытую максимальным числом отрезков
    • Найти количество пар пересекающихся отрезков
    • Для каждого задача найти количество пересекающихся с ним
    • Даны \(n\) отрезков на прямой. Для каждого \(k\) от \(0\) до \(n\) посчитать длину части прямой, покрытой ровно \(k\) отрезками.
  • Задачи на сортировку, придумывание компаратора

    • Примеры на сортировку, сортировку по сумме, сортировку по частному
    • Задача о двух станках
    • Метод доказательства поставим максимум на первое место
    • Метод доказательства поменяем местами два соседних, ответ улучшится