UVa 10125 - Sumsets

本文主要是介绍UVa 10125 - Sumsets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

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

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)

/** 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)

/** 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 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\n", ans);else printf("no solution\n");}return 0;
}

—— 生命的意义，在于赋予它意义。

原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)