Решение задачи Выбор напитков с Codeforces

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


Старожилы ЛКШ могут помнить смены, в которых каждый школьник получал на вечёрку желаемый напиток. Или не совсем?

В домике живёт n школьников, каждый из них в анкете отметил свой любимый напиток ai. Таким образом, известны n целых чисел a1,a2,…,an, где ai (1≤ai≤k) — номер любимого напитка i-го школьника. Все напитки пронумерованы от 1 до k.

В наличии есть неограниченное количество наборов напитков. Каждый набор содержит ровно две порции одинакового напитка. Иными словами, в наличии есть k типов наборов, j-й набор содержит две порции напитка j. Количество наборов каждого из k типов — неограниченно.

Известно, что на домик будет выдано наименьшее количество наборов, но при этом достаточное, чтобы хватило всем школьникам. Конечно, количество наборов будет равно ⌈n2⌉, где ⌈x⌉ обозначает округление вверх числа x.

После получения наборов школьники самостоятельно разберут порции. Заметим, что если n является нечётным числом, то одна порция останется лишней и её выпьет преподаватель.

Какое наибольшее количество школьников смогут получить любимый напиток при оптимальном выборе ⌈n2⌉ наборов и распределении порций между школьниками?

Код

#include<bits/stdc++.h>
using namespace std;
int n,k,a,o,c[2000];
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		c[a]++;
	}
	for(int i=0;i<=k;i++)
		if(c[i]%2)
			o++;
	cout<<n-o/2;
	return 0;
}

         

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



Комментарии

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