UVa 10125 - Sumsets

类型：哈希，二分查找

原题：
Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.
Input
Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.
Output
For each S, a single line containing d, or a single line containing "no solution".
Sample Input
5
2
3
5
7
12
5
2
16
64
256
1024
0
Output for Sample Input
12
no solution

题目大意;
给一个在 -536870912和536870911之间的整数集合S，找出 a + b + c = d , 最大的一个d输出。其中a,b,c,d都属于集合S，并且它们各不相同。

分析与总结:
最朴素的做法是三层for循环，复杂度O（n^3）, 而n最大是1000，势必会超时的。所以需要把 a + b + c = d 转换成d-c = a+b.
其中a+b 可以事先求出来，那么就可以用两层for循环枚举d和c，复杂度变成了O(n^2).
这题关键的一个地方在于判断a,b,c,d是不是不同的数，所以在计算a+b的和时，还要把a和b在集合S中的下标记录下来，可以用一个结构题猜存。把集合a+b看作是Sum，然后枚举t=d-c, 判断t是否在Sum中，如果在的话，还要判断d,c的坐标是否和Sum中等于t的元素的下标是否有冲突。

第一种查找方法是先把Sum排序，然后直接二分查找。运行时间为：0.112s (UVa)， 250MS (poj)
[cpp]
/*
* UVa 10125 - Sumsets
* 二分查找版
* Time: 0.112s (UVa)， 250MS (poj)
* Author: D_Double
*
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
const int MAXN = 1003;
using namespace std;

int S[MAXN], n, ans;

struct Node{
    int sum;
    int a, b;
    friend bool operator < (const Node &a, const Node &b){
        return a.sum < b.sum;
    }
};
Node sum[MAXN*MAXN];
int rear;

bool solve(){
    Node tmp;
    ans = -2147483646;
    for(int i=n-1; i>=0; --i){
        for(int j=0; j<n; ++j)if(i!=j){
            int t = S[i]-S[j];
            tmp.sum = t; tmp.a=i; tmp.b=j;
            Node* p = lower_bound(sum, sum+rear, tmp);
            if(p->sum==t && S[i]>ans){
                while(p->sum == t){
                    if(p->a!=i && p->a!=j && p->b!=i && p->b!=j){
                        ans = S[i]; // 因为S[i]是从大到小枚举的，所以一旦找到就一定是最大的
                        return true;
                    }
                    ++p;
                }
            }
        }
    }
    return false;
}

int main(){
    while(scanf("%d",&n), n){
        for(int i=0; i<n; ++i) scanf("%d", &S[i]);
        sort(S, S+n);
        rear = 0;
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j)if(i!=j){
                sum[rear].sum = S[i]+S[j];
                sum[rear].a=i, sum[rear++].b=j;
            }
        }
        sort(sum, sum+rear);
        if(solve()) printf("%d\n", ans);
        else printf("no solution\n");
    }
    return 0;
}

第二种方法是用哈希来查找。
用哈希表要注意，由于数据范围是-536870912～536870911，有负数，所以要让每个值先加上536870912转换成非负数，那么数据范围就变成了0～536870912+536870911，然后再进行哈希转码，很明显两个数字相加可能超过32位int范围，所以用long long
运行时间为: 0.080s(uva) , 219MS (poj)
[cpp]
/*
* UVa 10125 - Sumsets
* 哈希版
* Time: 0.080 s (UVa), 219 MS(poj)
* Author: D_Double
*
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
const int MAXN = 1003;
const long long ADD = 536870912;
using namespace std;

int n, S[MAXN], ans;

struct Node{
    long long sum; // 要用long long
    int a, b;
};

Node sum[MAXN*MAXN];
int rear;

const int HashSize = MAXN*MAXN;
int head[HashSize], next[MAXN*MAXN];

inline void init_lookup_table(){
    rear=1;
    memset(head, 0, sizeof(head));
}

inline int hash(long long key) {
    return (int)((key & 0x7FFFFFFF) % HashSize);
}

inline bool try_to_insert(int s){
    int h = hash(sum[s].sum);
    int u = head[h];
    while(u){
        u = next[u];
    }
    next[s] = head[h];
    head[h] = s;
    return true;
}

inline bool search(Node &s){
    int h = hash(s.sum);
    int u = head[h];
    while(u){
      &nbs

补充：软件开发 , C++ ,