Что: Семинар
Когда: Пятница, 16 сентября 2016, 18:30–20:00
Где: Таймс, 4 этаж

Описание

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

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

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

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

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

Материалы

Подробный план и код, написанный на лекции

http://acm.math.spbu.ru/~sk1/courses/1617f_cscenter/plans/2016-09-16-SortGreedy.html