问题 22755. -- 谁会赢?

22755: 谁会赢?

时间限制: 1 Sec  内存限制: 128 MB
献花: 13  解决: 1
[献花][花圈]

题目描述

最近,在课余时间流行这样一种游戏,游戏的规则如下:游戏开始时,每个人都从规定范围内的数中选取一个数(保证所选取的数各不相同),写在纸上,握在手中(以防让别的同学看见),然后同时打开,如果其中一个同学手中的数是其它任意两位同学手中的数之和,那么他就赢,如果满足条件的有多个,手中的数最大的那位同学赢!这是心理和智力的双重考验,所以参加的学生越来越多,但是,由于参与人数众多,要判断谁赢就成了问题,于是同学们请聪明的你设计一个程序来解决这个问题!

输入

 输入文件game.in的第一行为一个整数N(3<=N<=50000),表示参加游戏的总人数,第二行为N个数(范围在0~2^31之间),依次表示N个同学所选的数,第i个数表示第i位同学所选的数。

输出

  输出文件game.out只一行,为一个整数,表示那位同学赢。如果没有任何一位同学赢,则输出“0”。

样例输入

 5            //参加游戏的总人数
 2 5 7 3 13   //表示第一个同学选的数是2,第二个同学选取的数是5,…

样例输出

3	//表示第3位同学赢,因为7=5+2,并且最大

提示


【数据规模】



 30%的数据:N<=500



 60%的数据:N<=5000



 100%的数据:N<=50000





第四课:有一定难度,考察学生排序、二分查找、贪心的相关知识。



方法一:暴力枚举:可以过3个点。



方法二:排序(O(N^2))后,用贪心算法(如下),可以过6个点。



  for i:=n downto 3 do



    for j:=n-1 downto 2 do



      for k:=1 to j-1 do



         if a[i,1]=(a[j,1]+a[k,1])



           then begin



                  writeln(a[i,2]);



                  halt;



                end;



方法三:排序后(O(N^2)),用二分查找,可以过8个点。



方法四:快排后,用二分查找可以过去10个点。





来源

[献花][花圈]