题解：UVA10125 Sumsets

题意：给一个有 $n$ 个数的集合 $S$，找出一个最大的 $d$ 满足 $a+b+c=d$，$a$，$b$，$c$，$d$ 为集合中不同的数。

思路：

首先，如果你暴力枚举四个数，理论上是会超时的，但是过了。

代码如下，只是加了一点小优化：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
int a[N];
signed main(){
	while(scanf("%d",&n)){
		if(n==0)break;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1,greater<int>());//从大到小排序，下面从大到小遍历
		bool flag=false;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j)continue;//相同的数字
				for(int k=j+1;k<=n;k++){
					if(i==k)continue;//相同的数字
					for(int l=k+1;l<=n;l++){
						if(l==i)continue;//相同的数字
						if(a[i]==a[j]+a[k]+a[l]){//a[i]就是最大的d
							printf("%d\n",a[i]);
							flag=true;//找到答案标记
							break;
						}
					}
					if(flag)break;
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(!flag)printf("no solution\n");//未标记也就是无解
	}
	return 0;
}
```
这个方法应该都能想出来。[记录](https://www.luogu.com.cn/record/215547556)。

然后，$n \le 1000$，那么正解的时间复杂度应为 $\mathcal O( t n ^ 2)$。

很简单的，把 $c$ 移项到左边，使等式成为 $a+b=d-c$，枚举 $a+b$ 后并记录 $a$ 和 $b$。再枚举 $d-c$，再寻找有没有记录过相等的 $a+b$，再判断四个数是否不同。

代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
int s[N];
signed main(){
	while(scanf("%d",&n)){
		if(n==0)break;
		for(int i=1;i<=n;i++)scanf("%d",&s[i]);
		map<int,pair<int,int> >mp;
		sort(s+1,s+n+1);
		for(int i=1;i<=n;i++){//枚举a+b并记录
			for(int j=i+1;j<=n;j++){
				mp[s[i]+s[j]]={s[i],s[j]};
			}
		}
		bool flag=false;
		for(int i=n;i>=1;i--){//从大到小遍历d
			for(int j=1;j<=n;j++){
				if(i==j)continue;//相同的数字
				int a=mp[s[i]-s[j]].first;
				int b=mp[s[i]-s[j]].second;
				if(a+b!=s[i]-s[j]||a==s[i]||a==s[j]||b==s[i]||b==s[j])continue;//判断是否有a+b=d-c并判断是否有相同数字
				printf("%d\n",s[i]);
				flag=true;//标记
				break;
			}
			if(flag)break;
		}
		if(!flag)printf("no solution\n");//未标记即无解。
	}
	return 0;
}
```
[记录](https://www.luogu.com.cn/record/215547435)。大概是因为用 map，导致时间比暴力还慢。