UVa 10125：Sumsets

UVa 10125：Sumsets2014-10-09 shuangde800 题目链接：

UVa : http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1066

poj : http://poj.org/problem？id=2549

类型：哈希，二分查找

原题：

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

52 3 5 7 1252 16 64 256 10240

Output for Sample Input

12no 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）

/** UVa10125 - 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
", ans）;else printf（"no solution
"）;}return 0;}

第二种方法是用哈希来查找。

用哈希表要注意，由于数据范围是-536870912～536870911，有负数，所以要让每个值先加上536870912转换成非负数，那么数据范围就变成了0～536870912+536870911，然后再进行哈希转码，很明显两个数字相加可能超过32位int范围，所以用long long

URL：http://www.bianceng.cn/Programming/sjjg/201410/45670.htm

运行时间为: 0.080s（uva） , 219MS （poj）

/** UVa10125 - 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 longint 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）{if（sum[u].sum==s.sum && sum[u].a！=s.a && sum[u].a！=s.b && sum[u].b！=s.a && sum[u].b！=s.b）{return true;}u = next[u];}return false;} bool solve（）{Node tmp;ans = -2147483646;for（int i=n-1; i>=0; --i）{for（int j=0; j<n; ++j）if（i！=j）{long long t = S[i]-S[j] + ADD + ADD;tmp.sum = t;tmp.a=i; tmp.b=j;if（search（tmp）） {ans = S[i]; return true;}}}return false;} int main（）{while（scanf（"%d",&n）, n）{for（int i=0; i<n; ++i） scanf（"%d", &S[i]）; sort（S, S+n）;init_lookup_table（）;for（int i=0; i<n; ++i）{for（int j=0; j<n; ++j）if（i！=j）{sum[rear].sum = S[i]+ADD+S[j]+ADD;sum[rear].a=i; sum[rear].b=j;try_to_insert（rear）;++rear;}}if（solve（）） printf（"%d
", ans）;else printf（"no solution
"）;}return 0;}