類型： 哈希， 二分查找
原題：
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){
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;
}
