题目分析

我们需要在给定的整数集合 $S$ 中，找到最大的元素 $d$，使得存在三个互不相同的元素 $a$, $b$, $c \in S$ 满足 $a + b + c = d$。如果不存在这样的 $d$，则输出 no solution。

解题思路

1. 排序预处理：

   • 将集合 $S$ 按降序排列，这样我们可以优先检查较大的 $d$，确保找到的第一个解就是最大的可能解。

2. 枚举 $d$ 和 $a$：

   • 外层循环枚举可能的 $d$（即 $S$ 中的每个元素）。
   • 内层循环枚举可能的 $a$（同样是 $S$ 中的元素），并计算 $t = d - a$，即 $b + c$ 的目标值。

3. 双指针查找 $b$ 和 $c$：

   • 对于固定的 $d$ 和 $a$，使用双指针法在剩余元素中查找 $b$ 和 $c$，使得 $b + c = t$。
   • 指针初始化：$left = j + 1$，$right = n - 1$。
   • 如果 $b + c > t$，则右指针左移（$right--$）。
   • 如果 $b + c < t$，则左指针右移（$left++$）。
   • 如果 $b + c = t$，检查 $d$, $a$, $b$, $c$ 是否互不相同。若满足条件，则记录 $d$ 并退出循环。

4. 提前终止：

   • 一旦找到满足条件的 $d$，立即终止所有循环，输出结果。

关键代码解析

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

long long da[1020];
int main()
{
	while(1)
	{
		int n;
		scanf("%d",&n);
		if(n==0)
		{
			break;
		}
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&da[i]);
		}
		sort(da,da+n,greater<int>());
		int flag=0;
		int mx;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)//
			{
				if(i!=j)
				{
					int left=j+1,right=n-1;
					long long t=da[i]-da[j];
					while(left<right)
					{
						if(t>da[left]+da[right])
						{
							right--;
						}else if(t<da[left]+da[right])
						{
							left++;
						}else
						{
							if(i!=left&& i!=right)//
							{
								flag=1;
								mx=da[i];
								break;								
							}
						}
					}
					if(flag==1)
					{
						break;
					}
				} 
			}
			if(flag==1)
			{
				break;
			}
		}
		if(flag==1)
		{
			cout<<mx<<endl;
		}else
		{
			cout<<"no solution"<<endl;
		}
	} 
	return 0;
}