/**//*
:8080/online/?action=problem&type=show&id=10181
*/
#include<cstdio>
#include<cstdlib>
usingnamespacestd;
structs
{
inta;//前一个操作数的下标
intb;//后一个操作数的下标
intvalue;//存储操作后的值
};
intn;
ssub1[499501];
ssub2[499501];
intdata[1001];
intnum=0;
intcomp(constvoid*aa,constvoid*bb){
structs*a=(s*)aa;
structs*b=(s*)bb;
returna->value-b->value;
}
intFindSub2(intstart,intend,intvalue)
{
intleft=start;
intright=end-1;
intmid;
while(left<=right)
{
mid=(left+right)/2;
if(sub2[mid].value==value)
returnmid;
elseif(sub2[mid].value>value)
right=mid-1;
else
left=mid+1;
}
return-1;
}
voidReadInfo()
{
for(inti=0;i<n;i++)
{
scanf("%d",&data[i]);
}
}
//存储+，-的值
voidStoreValue()
{
inti,j;
num=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
sub1[num].a=i;
sub1[num].b=j;
sub1[num].value=data[i]+data[j];
inttmpi,tmpj;
if(data[i]>data[j])
tmpi=i,tmpj=j;
else
tmpi=j,tmpj=i;
sub2[num].a=tmpi;
sub2[num].b=tmpj;
sub2[num].value=data[tmpi]-data[tmpj];
num++;
}
}
}
intFindD()
{
inti,j;
intmax=-0x7FFFFFFF;
qsort(sub1,num,sizeof(structs),comp);
qsort(sub2,num,sizeof(structs),comp);
intstart=0;
for(i=0;i<num;i++)
{
while(start<num&&sub2[start].value<sub1[i].value)
start++;
if(start>=num)
break;
intindex=FindSub2(start,num,sub1[i].value);
if(index==-1)
continue;
if(sub2[index].a==sub1[i].a||sub2[index].a==sub1[i].b
||sub2[index].b==sub1[i].a||sub2[index].b==sub1[i].b)
continue;
if(max<data[sub2[index].a])
max=data[sub2[index].a];
}
returnmax;
}
intmain()
{
inti,j;
while(scanf("%d",&n)!=EOF&&n)
{
ReadInfo();
StoreValue();
intd=FindD();
if(d==-0x7FFFFFFF)
printf("nosolution\n");
else
printf("%d\n",d);
}
return0;
} 我是这样做的，存储所有的和和差的情况(差只取正值)， 然后遍历和，用二分去查找差中是否存在和。
刚开始使用的是lower_bound，目测大约有10秒以上，自己写了一个二分，一下快多了。听kaikai说，STL在debug和release相差的很多，汗。。。
