问题 T: 【排序】谁会赢？

时间限制: 3 Sec  内存限制: 64 MB

题目描述

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

 

输入

第1行为一个整数N(3≤N≤50000)，表示参加游戏的总人数，第2行为N个数（范围在0～2^31之间），依次表示N个同学所选的数，第i个数表示第i位同学所选的数。

 

输出

只一行，为一个整数，表示哪位同学赢。如果没有任何一位同学赢，则输出“0”。

 

样例输入

复制样例数据

5
2 5 7 3 13

样例输出

3

 

提示

 

100%的数据：N≤50000

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
map<LL, int> mp;

struct node
{
	int id;
	LL num;
	bool operator <(const node &x)const{
		return num < x.num;
	}
}a[50005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i].num), a[i].id = i, mp[a[i].num] = 1;
	sort(a + 1, a + 1 + n);
	int flag = 0;
	for (int i = n; i >= 1; i--){ //预先把所有可能情况存起来会暴空间
		if(flag) break;
		for (int j = i - 1; j >= 1; j--){
			if(mp[a[i].num - a[j].num] && 2 * a[j].num != a[i].num && a[j].num != 0){//少一个条件就错
				printf("%d\n", a[i].id);
				flag = 1;
				break;
			}
		}
	}
	if(!flag) printf("0\n");

	return 0;
}
/**/