Codeforces 1250B - The Feast and the Bus（枚举 + 贪心）

Employees of JebTrains are on their way to celebrate the 256-th day of the year! There are n employees and k teams in JebTrains. Each employee is a member of some (exactly one) team. All teams are numbered from 1 to k. You are given an array of numbers t1,t2,…,tn where ti is the i-th employee’s team number.

JebTrains is going to rent a single bus to get employees to the feast. The bus will take one or more rides. A bus can pick up an entire team or two entire teams. If three or more teams take a ride together they may start a new project which is considered unacceptable. It’s prohibited to split a team, so all members of a team should take the same ride.

It is possible to rent a bus of any capacity s. Such a bus can take up to s people on a single ride. The total cost of the rent is equal to s⋅r burles where r is the number of rides. Note that it’s impossible to rent two or more buses.

Help JebTrains to calculate the minimum cost of the rent, required to get all employees to the feast, fulfilling all the conditions above.

Input

The first line contains two integers n and k (1≤n≤5⋅10⁵,1≤k≤8000) — the number of employees and the number of teams in JebTrains. The second line contains a sequence of integers t1,t2,…,tn, where ti (1≤ti≤k) is the i-th employee’s team number. Every team contains at least one employee.

Output

Print the minimum cost of the rent.

Examples
Input
6 3
3 1 2 3 2 3
Output
6
Input
10 1
1 1 1 1 1 1 1 1 1 1
Output
10
Input
12 4
1 2 3 1 2 3 4 1 2 1 2 1
Output
12

题目大意：

先输出n和k，表示有n个人和k个团队，接下来的n个数，每个数输入该编号的人属于哪个团队，团队要组织旅游，只能租一辆车，一辆车最多装2个团队，且团队不能拆分，车费 = 车的容量 * 乘车次数（不计返回），求最小车费。

解题思路：

可以先将每个团队的人数排个序，团队不能拆分，而且每次最多装2个团队，那么，车的最小容量应该是a[0]，最大容量则是a[0] + a[1]，枚举a[0] - a[1] 之间的数，去计算乘车次数，如果乘车次数恰好 = ⌊ k / 2 ⌋，则说明每次都能装2个团队，最多有一次装1个团队，即可退出循环（省时），暴力枚举即可。注意开long long ，WA了一次。

Code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int mod = 1e9 + 7;
const int N = 8050;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, double> pid;
ll g[N], n, k;
ll ceil(ll s)
{
	ll res = 0;
	int l = 1, r = k;
	while (l <= r)
	{
		if (g[l] + g[r] <= s)
		  l++, r--;
		else
		  l++;
		res++;
	}
	return res;
}
int main()
{
	memset(g, 0, sizeof g);
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
	{
		int s;
		cin >> s;
		g[s]++;
	}
	if (n == 1)
	{
		cout << n << endl;
		return 0;
	}
	sort(g + 1, g + k + 1, greater<int>() );
	ll ans = k * 5000000;
	for (ll i = g[1]; i <= g[1] + g[2]; i ++)
	{
		ll r = ceil(i);
		ans = min(ans, i * r);
		if (r == ceil(k / 2.0))
		  break;
	}
	cout << ans << endl;
	return 0;
}