Задача взята с сайта e-olymp
Задача
Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.
Входные данные
В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.
Выходные данные
Вывести максимально возможное количество квадратов, которое можно составить из заданных отрезков.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 1 | 9 2 2 4 2 3 2 1 2 4 |
1 |
| 2 | 11 2 2 4 2 2 4 2 2 1 2 2 |
2 |
| 3 | 5 8 9 8 9 11 |
0 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #define MAX 101 using namespace std; int a[MAX]; int main() { int n, l, res = 0, i; cin >> n; for(l = 0; l < n; l++) cin >> i, a[i]++; for(i = 1; i <= MAX - 1; i++) res += a[i] / 4; cout << res << "\n"; return 0; } |
Решение
Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$ до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$
Для этого совершим сортировку подсчетом. В ячейке
a[i] подсчитываем количество отрезков длины
i . В переменную
res подсчитываем количество квадратов, которое можно построить.
Ссылки
Условие задачи на e-olymp
Код программы на ideone
Сортировка подсчетом на Wikipedia