GHOJ 230 谁会赢？

题目描述

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

输入输出格式

输入格式

第一行为一个整数N（3≤N≤50000），表示参加游戏的总人数，第二行为N个数（范围在0-

输出格式

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

输入输出样例

输入样例

2 5 7 3 12

输出样例

题解

朴素做法是枚举两个数，然后判断第三个数是否存在，用map能做到O(n²logn)的时间复杂度，但显然这种做法不满足题目需求。

我们可以换一个角度思考，枚举和，然后枚举加数，加数实际上可以用一重循环就枚举出来。我们可以排序之后不断缩小枚举区间来找加数，这样就能做到O(n²)的时间复杂度。具体看下面的代码。

#include <iostream>
#include <cstdio>

#define MAX_N 50001

using namespace std;

int n;
struct Node
{
    int idx;
    int val;
};
Node a[MAX_N | 1], b[MAX_N | 1];

void Sort(int lt, int rt)
{
    if(lt == rt) return;
    int mid = lt + rt >> 1;
    Sort(lt, mid);
    Sort(mid + 1, rt);
    int i = lt, j = mid + 1;
    int cnt = 0;
    while(i <= mid && j <= rt)
    {
        if(a[i].val < a[j].val) b[++cnt] = a[i++];
        else b[++cnt] = a[j++];
    }
    while(i <= mid)
    {
        b[++cnt] = a[i++];
    }
    while(j <= rt)
    {
        b[++cnt] = a[j++];
    }
    for(i = 1; i <= cnt; ++i)
    {
        a[lt + i - 1] = b[i];
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)    
    {
        scanf("%d", &a[i].val);
        a[i].idx = i;
    }
    Sort(1, n);
    for(register int k = n; k; --k)
    {
        for(register int i = 1, j = k - 1; i < j;)
        {
            while(i < j && a[i].val + a[j].val < a[k].val) ++i;
            while(i < j && a[i].val + a[j].val > a[k].val) --j;
            if(a[i].val + a[j].val == a[k].val) return printf("%d", a[k].idx), 0;
        } 
    }
    putchar('0');
    return 0;
}

参考程序O(n²)版

我们可以发现，我们不断缩小的区间本身就是满足单调性的，那我们其实可以用二分查找来缩小区间，这样子在题库给的数据下更快，使时间复杂度降到O(OK)。

#include <iostream>
#include <cstdio>

#define MAX_N 50001

using namespace std;

int n;
struct Node
{
    int idx;
    int val;
};
Node a[MAX_N | 1], b[MAX_N | 1];

int Read()
{
    int res = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res;
}

void Sort(int lt, int rt)
{
    if(lt == rt) return;
    int mid = lt + rt >> 1;
    Sort(lt, mid);
    Sort(mid + 1, rt);
    int i = lt, j = mid + 1;
    int cnt = 0;
    while(i <= mid && j <= rt)
    {
        if(a[i].val < a[j].val) b[++cnt] = a[i++];
        else b[++cnt] = a[j++];
    }
    while(i <= mid)
    {
        b[++cnt] = a[i++];
    }
    while(j <= rt)
    {
        b[++cnt] = a[j++];
    }
    for(i = 1; i <= cnt; ++i)
    {
        a[lt + i - 1] = b[i];
    }
    return;
}

int main()
{
    n = Read();
    for(register int i = 1; i <= n; ++i)    
    {
        a[i].val = Read();
        a[i].idx = i;
    }
    Sort(1, n);
    int lt, rt, mid;
    int op;
    for(register int k = n; k; --k)
    {
        for(register int i = 1, j = k - 1; i < j;)
        {
            op = 0;
            if(a[i].val + a[j].val < a[k].val) 
            {
                lt = i + 1;
                rt = j - 1;
                while(lt <= rt)
                {
                    mid = lt + rt >> 1;
                    if(a[mid].val + a[j].val < a[k].val) lt = mid + 1;
                    else op = 1, i = mid, rt = mid - 1;
                }
            }
            if(a[i].val + a[j].val > a[k].val) 
            {
                lt = i + 1;
                rt = j - 1;
                while(lt <= rt)
                {
                    mid = lt + rt >> 1;
                    if(a[i].val + a[mid].val > a[k].val) rt = mid - 1;
                    else op = 1, j = mid, lt = mid + 1;
                }
            }
            if(a[i].val + a[j].val == a[k].val) 
            {
                printf("%d", a[k].idx);
                return 0;
            }
            if(!op) break;
        } 
    }
    putchar('0');
    return 0;
}

参考程序O(OK)版