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解题报告
3. **算法与数据结构**:700题涵盖的范围广泛,涉及基本的排序算法(如冒泡、快速、归并排序),查找算法(如二分查找),以及高级算法如动态规划(如斐波那契数列、背包问题)、图论(如最短路径、最小生成树)、...
zoj题目简单归类zoj题目简单归类zoj题目简单归类
"POJ 计算几何入门题目.doc"可能介绍了计算几何的基础知识,并提供了一些实践题目,这个领域涉及点、线、面的相互关系,以及在二维和三维空间中的几何操作。 5. **ZOJ题目分类**: "zoj题目分类.doc"对应浙江大学...
acm中zoj1002的可运行C++程序
首先,我们可以从这些源代码中学习到基础的算法思想,如排序算法(快速排序、归并排序、冒泡排序、插入排序等)、搜索算法(二分查找、深度优先搜索、广度优先搜索等)。这些算法是解决问题的基本工具,理解和掌握...
Problem Arrangement zoj 3777
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...
2. ZOJ Problem Set – 1037 Gridland 该题目主要考察了数组和矩阵的操作能力,要求解决 Gridland 问题。该问题的解决需要对数组和矩阵的操作有深入的理解。 知识点:数组、矩阵、数组操作、矩阵操作。 3. ZOJ ...
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
1. **基础算法**:包括排序(如快速排序、归并排序)、搜索(如二分查找)、动态规划、贪心算法、回溯算法等。 2. **高级数据结构**:如链表、树(二叉树、平衡树如AVL和红黑树)、图(深度优先搜索、广度优先搜索...
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
1. **基础算法**:作为入门部分,这个集合可能包括基础数据结构和算法,如排序(快速排序、归并排序、堆排序)、查找(二分查找、哈希表查找)以及图论的基本概念(Dijkstra、Floyd等)。这些是所有ACM竞赛者必须...
zoj4041正确题解源代码,以及运行程序
标题 "zoj 1140-zju 2433 简单题的部分答案" 暗示了这是一个关于编程竞赛题目的解答集合,其中涵盖了ZOJ(浙江大学在线评测系统)上的两道题目——ZOJ 1140 和 ZJU 2433。这些题目可能属于算法或数据结构的范畴,...