Решение задачи Перестановка массива с Codeforces

Без пояснения   Просмотров: 82


Дан массив целых чисел. Вася может переставлять его числа местами. При этом он хочет, чтобы как можно больше чисел стояли там, где раньше стояли меньшие числа. Помогите ему найти максимальное количество таких чисел.

Например, если нам дан массив [10,20,30,40], мы можем переставить числа так, что массив станет [20,40,10,30]. При этом на первой и второй позициях числа стали больше (20>10, 40>20), а на третьей и четвёртой — нет, значит для такой перестановки число, которое хочет максимизировать Вася, равно 2. Ознакомьтесь с примечанием к первому тестовому примеру, там разобран ещё один показательный тест.

Помогите Васе так переставить числа, чтобы количество позиций, в которых в новом массиве числа больше, чем в изначальном, было максимальным.

Код

#include <bits/stdc++.h>
using namespace std;

int n, t, ans;
map<int, int> mmp;

int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d", &t);
		mmp[t]++;
		ans=max(ans, mmp[t]);
	}
	printf("%d\n", n-ans);
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться