3140020_ac_938ms_11500k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#define inf -2100000000

struct node
{
	int a, b, c;
};

node sum[1000011], dif[1000011];
int ns, nd;
int num[1011];

int cmp(const void *a,const void *b)
{
	node *aa = (node *)a;
	node *bb = (node *)b;
	return aa->c - bb->c;
}

int main()
{
	int n, i, j, ans;
	node *p, *q, t;

	while(scanf("%d",&n)==1,n)
	{
		for(i = 0; i < n; i++)
		{
			scanf("%d",&num[i]);
		}
		if(n < 4)
		{
			puts("no solution");
			continue;
		}
		ans = inf;
		ns = 0;
		for(i = 0; i < n; i++)
		{
			for(j = i+1; j < n; j++)
			{
				sum[ns].a = num[i];
				sum[ns].b = num[j];
				sum[ns].c = num[i]+num[j];
				ns++;
			}
		}
		nd = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(i!=j)
				{
					dif[nd].a = num[i];
					dif[nd].b = num[j];
					dif[nd].c = num[i]-num[j];
					nd++;
				}
			}
		}
		qsort(dif,nd,sizeof(dif[0]),cmp);
		for(i = 0; i < ns; i++)
		{
			p = (node *)bsearch(&sum[i],dif,nd,sizeof(dif[0]),cmp);
			if(p!=NULL)
			{
				q = p;
				while(q!=dif&&(*q).c==(*p).c)
				{
					t = *q;
					if(t.a!=sum[i].a&&t.a!=sum[i].b&&t.b!=sum[i].a&&t.b!=sum[i].b)
					{
						if(t.a > ans)
						{
							ans = t.a;
						}
					}
					q--;
				}
				q = p;
				while((++q)!=&dif[nd]&&(*q).c==(*p).c)
				{
					t = *q;
					if(t.a!=sum[i].a&&t.a!=sum[i].b&&t.b!=sum[i].a&&t.b!=sum[i].b)
					{
						if(t.a > ans)
						{
							ans = t.a;
						}
					}
					q++;
				}
			}
		}
		if(ans==inf)
			puts("no solution");
		else
			printf("%d\n",ans);
	}
	return 0;
}