Задача
У продавца воздушных шариков есть [latex]n[/latex] шаров. Каждый из них имеет некоторый цвет. Однако совсем недавно Три Толстяка издали указ, разрешающий торговать шариками какого-то одного цвета. Чтобы не нарушать закон, но при этом и не потерять прибыль, продавец решил перекрасить некоторые из своих шариков.
Напишите программу для определения минимального количества перекрашиваний.
Входные данные
В первой строке задано количество шаров [latex]n (1\leqslant n \leqslant 100000)[/latex]. Вторая строка состоит из [latex]n[/latex] целых чисел, в пределах от 1 до 9, определяющие цвета шаров (1 — синий, 2 — зеленый, 3 — голубой, 4 — красный, 5 — розовый, 6 — желтый, 7 — серый, 8 — черный, 9 — белый).
Выходные данные
Выведите минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 4 3 1 2 1 | 2 |
| 2 | 1 1 | 0 |
| 3 | 6 1 1 1 2 2 2 | 3 |
| 4 | 3 1 2 3 | 2 |
| 5 | 4 3 3 3 8 | 1 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int n,tmp,cl1,cl2,cl3,cl4,cl5,cl6,cl7,cl8,cl9; int main(){ cin >> n; for(auto i = 0; i < n; ++i){ cin >> tmp; (tmp==1) ? ++cl1 : (tmp==2) ? ++cl2 : (tmp==3) ? ++cl3 : (tmp==4) ? ++cl4 : (tmp==5) ? ++cl5 : (tmp==6) ? ++cl6 : (tmp==7) ? ++cl7 : (tmp==8) ? ++cl8 : ++cl9; } cout << n-max(cl1,max(cl2,max(cl3,max(cl4,max(cl5,max(cl6,max(cl7,max(cl8,cl9)))))))); } |
Решение задачи
Для того, чтобы найти количество шариков, которые необходимо перекрасить, нужно узнать максимальное количество шариков одного цвета и из общего количества шариков n вычесть найденный максимум. Для нахождения максимума считываем номер цвета шара в цикле и увеличиваем соответствующую переменную cl на единицу. По окончанию цикла ищем максимальное количество шаров одного цвета и выводим n-max.