Решение задачи Коробка с конфетами (легкая версия) с Codeforces

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

Фактически эта задача является подзадачей задачи G из этого контеста.

В коробке с конфетами находятся n конфет. Тип i-й конфеты равен ai (1≤ai≤n).

Вы хотите приготовить подарок, используя некоторые из этих конфет, со следующим ограничением: количества конфет каждого типа, находящегося в подарке, должны быть различны (то есть, например, подарок, имеющий две конфеты типа 1 и две конфеты типа 2 является плохим).

Возможно, что некоторые типы конфет могут вообще не находиться в подарке. Также возможно, что не все конфеты каких-то типов будут взяты в подарок.

Ваша задача — найти максимально возможный размер одного подарка, который Вы можете приготовить, используя конфеты, которые Вы имеете.

Вам необходимо ответить на q независимых запросов.

Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

Код 

#include<bits/stdc++.h>
using namespace std;
int q,n,a[400000],l,ans,t;
int main()
{
	cin>>q;
	while(q--)
	{
		cin>>n;
		ans=0;
		for(int i=0;i<=n;i++)
			a[i]=0;
		for(int i=0;i<n;i++)
		{
			cin>>t;
			a[t]++;
		}
		sort(a,a+n+1);
		l=a[n];
		for(int i=n;i>0;i--)
		{
			t=min(a[i],l);
			ans+=max(t,0);
			l=t-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp