zcmu:
1098: 查找元素
Time Limit: 1 Sec Memory Limit: 128 MB
[Submit][Status][Web Board]
Description
給定一個整數集合s,對于s裡的不同元素a,b,c,d,找出一個最大的d,滿足a+b+c=d.
Input
多組測試資料,每組第一行為一個正整數n.(1<=n<=1000)代表集合中元素的個數,第二行為n個整數代表集合裡的元素.(每個整數的絕對值小于等于10^8)
Output
對于每組資料如果d存在輸出最大的d,否則輸出”no solution”.
Sample Input
5
2
3
5
7
12
5
2
16
64
256
1024
Sample Output
12
no solution
HINT
Source
//這題要用逆向思維~
//(也是好久之前寫的)
Ac_code:
#include<stdio.h>
#include<algorithm>
using namespace std;
long a[1005];
int search_2(long a[],long a1,long a2,long a3,int n)
{
int top=0,tail=n-1,mid,f=-1;
long aim=a1-a2-a3;
while(top<=tail)
{
mid=(top+tail)/2;
if(aim<a[mid])
{
tail=mid-1;
}
else if(aim>a[mid])
{
top=mid+1;
}
else
{
if(aim!=a1&&aim!=a2&&aim!=a3)//這裡也是關鍵,要保證得到的目标值不是用過的數
{
f=mid;
}
break;
}
}
return f;
}
int main()
{
int n,i,j,k;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%ld",&a[i]);
}
sort(a,a+n);
int flag=0,w=-1;
for(j=n-1;j>=0;j--)
{
for( i=0;i<n;i++)//不要誤認為第一個減的不可以是他後面的,隻要他減的是都不相同的數就行
{
for(k=0;k<n;k++)
{
if(a[j]!=a[i]&&a[j]!=a[k]&&a[i]!=a[k])
w=search_2(a,a[j],a[i],a[k],n);
if(w!=-1)
{
flag=1;
printf("%ld\n",a[j]);
break;
}
}
if(flag==1) break;
}
if(flag==1) break;
}
if(flag==0) printf("no solution\n");
}
return 0;
}