#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x, v, sum, ans, res1, res2, res3, a[100005];
signed main()
{
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i], sum += a[i];
    if (a[i] > a[res1])
      res3 = res2, res2 = res1, res1 = i;
    else if (a[i] > a[res2])
      res3 = res2, res2 = i;
    else if (a[i] > a[res3])
      res3 = i;
  }
  swap(a[1], a[res1]), swap(a[2], a[res2]), swap(a[3], a[res3]);
  if (a[1] * 2 > sum - a[1])
  	cout << -1, exit(0);
  for (int i = 1; i <= n; i++)
    if (a[i] & 1)
      x++, a[i]--, sum--;
  if ((sum - a[1]) / 2 >= a[1])
  {
  	v = sum / 6;
	x += sum - v * 6;
  }
  else if (sum - a[1] - a[2] >= a[2])
  {
  	a[2] = a[3] = (sum - a[1]) / 2;
  	if (a[2] & 1)
      x += 2, a[2]--, a[3]--;
    x += a[1] - a[2];
    v = a[2] / 2;
  }
  else
  {
  	a[3] = sum - a[1] - a[2];
  	v = a[3] / 2;
  	x += a[1] + a[2] - 2 * a[3];
  }
  cout << min(v, v - (int)ceil((3 * v - x) / 9.0));
  exit(0);
}

代码如上，最优解

可以用数学归纳法来讨论 -1 的情况：（经过一番手推或者直接显然）如果有任意一个数字大于总数的三分之一，则无法使得每个人的姓名没有重复字，否则一定可以。

首先我们定义“相同字”的概念，如果某一个字出现了两次，分布在两个人名中，例如 wu-jia-han 和 wu-si-cheng 中，出现了两次的 wu 就是"相同字"。构成一个姓名团需要三个相同字。所以我们统计相同字的数量来判定姓名团的数量。

思路

假设某一个字库中的字能用 a[i] 次，那么它就能构成 a[i]/2 个相同字。

所以我们统计相同字的个数（即代码中的 ans），最终和可以构成的人数（sum/9，每个姓名团要 9 个字）求 min 来输出。

于是可以获得下面的错误代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<long long>a(n);
	long long sum = 0, allsum = 0, ans = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		allsum += a[i];
	}
	for(int i = 0; i < n; i++){
		ans += min(a[i] / 2, allsum / 9); // 这一步求 min 很关键，相同字数的贡献不能超过总人数。例如某个数字可以使用的次数是 allsum/3，虽然不会导致输出 -1，但它对答案的贡献也绝不是 a[i]/2。
		if(a[i] > allsum / 3){
			cout << -1 << endl;
			return 0;
		} 
	}
	cout << min(ans / 3, allsum / 9) << endl;
}

错误的 test 形如：

22
6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

应该输出 0，但上述代码输出 1。原因是 6 / 2 = 3，上述代码认为会产生 3 个相同字构成 1 个姓名团。但是由于一个合法人名中的三个字都不同，所以我们不能拿同一个 a[i] 产生的相同字去构造姓名团，应该用 3 个不同的 a[i] 产生的相同字构造。

如何保证每个姓名团都是用三个不同的 a[i] 构造的呢？我们可以利用鸽巢原理。例如我们总共有 $ans$ 个相同字，每个姓名团会用掉 3 个相同字，假设某一个 a[i] 产生的相同字大于 $ans/3$，那么显然在某一个姓名团中就会用掉两个相同字。这种情况是由于某一个 a[i] 过大造成的，例如上述 test 中其它数字都是 1，只有一个数字是 6，这个 6 显得过大。我们只能把 a[i] 中多余的部分舍弃，直到 a[i] 小于 $ans / 3$。（“多余的部分”指的是字库中一个字多余的出现次数，即消除“过大”的问题）

有多少个 a[i] 大于 $ans/3$ 呢？显然只有最大值和次大值可能大于 $ans/3$，所以我们只需要对最大的两个 a[i] 进行处理，舍弃多余的部分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[100009], sum, ans, b[2];
signed main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
	}
	for(int i = 1; i <= n; i++) {
		if(a[i] * 3 > sum){
			cout << -1;
			return 0;
		}
		ans += a[i] / 2;
		if(a[i] / 2 > b[0])// b[0] 存放最大, b[1] 存放次大
			b[0] = a[i] / 2;
		if(b[0] > b[1])
			swap(b[0], b[1]);
	}
	while(true) { // 防止减完次大值之后，最大值 * 3 又大于 ans，所以进行循环 
		bool flag = 1;
		for(int i = 0; i <= 1; i++) {
			if(b[i] * 3 > ans) {
				flag = 0;
				int x = (3 * b[i] - ans + 1) / 2; 
				// 找到最小的 x 使得 b[i] * 3 <= ans，推不出此公式可以使用更复杂的分类讨论，并代值验算其正确性 
				b[i] -= x;
				ans -= x;
			}
		}
		if(flag)	break;
	}
	cout << min(ans / 3, sum / 9);
	return 0;
}