Жадности. Время ввода/вывода. Разделяй и властвуй.

Задачи на сортировку и жадности

1. Есть работы. У каждой работы есть \(t_i\) -- время выполнения и \(f_i\) -- штраф. Нужно минимизировать \(\sum T_if_i\), где \(T_i\) -- момент выполнения работы.

2. Даны \(n\) отрезков на прямой. Для каждого \(k\) от \(0\) до \(n\) посчитать длину части прямой, покрытой ровно \(k\) отрезками.

3. Даны \(n\) гномов. Если \(i\)-го гнома укладывать спать \(a_i\) минут, он потом спит \(b_i\) минут. Можно ли сделать так, чтобы все гномы уснули?

4. Есть \(n\) спортсменов. \(i\)-й спортсмен имеет вес \(m_i\) и может держать на своих плечах суммарную массу \(s_i\). Можно ли построить башню из всех спортсменов?

5. Есть \(n\) работ. У каждой есть дедлайн \(d_i\) и время выполнения \(t_i\). Можно ли успеть выполнить все работы?

Будем тестировать время ввода/вывода.

1. C++ : cin/cout

2. C++ : scanf/printf

3. C++ : getchar/putchar

4. C++ : fread, fwrite

5. Java : Scanner, System.out

6. Java : BuffredReader, PrintWriter

Метод разделяй и властвуй

1. Сортировка слиянием и число инверсий (код)

2. Карацуба и умножение длинных чисел