http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=101
让你在一堆互不相同的数中查找是否有a=b+c+d,若有不同的解,则输出最大的。
思路:
排序后二分,从大到小枚举。设sum=a[index]-a[i]-a[j],然后查找sum是否在数组中存在即可。
二分要写对,然后i==j || index==j || index==i等于的情况要去除。
还有用goto从内重循环直接跳出,而不是用个标记一次次判断,简洁而优雅。
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1024;
int a[MAXN];
int n;
int search(int target)
{
int L=0,R=n-1;
while(L<R)
{
int mid=((L+R)>>1);
if(a[mid]==target)
return mid;
else if(a[mid] < target)
L=mid+1;
else
R=mid;
}
return -1;
}
int main()
{
while(~scanf("%d",&n),n)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int index;
for(index=n-1;index>=0;index--)
{
for(int i=0;i<n;i++)
{
if( i == index ) continue;
for(int j=0;j<n;j++)
{
if(i==j ||j==index)
continue;
int sum=a[index]-a[i]-a[j];
int id=search(sum);
if(id!=-1 && id!=i && id !=j && id != index)
{
printf("%d\n",a[index]);
goto end;
}
}
}
}
printf("no solution\n");
end:;
}
return 0;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢
能AC 通过的c++代码,包括zoj1002,1091,1789
zoj 1002 C语言的为什么描述要这么多字啊。。