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

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

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. Карацуба и умножение длинных чисел