求解a + b + c = d的d的最大值,已知输入的数不同。
变形为 a + b = d - c;
将a + b放入hash 通过堆来每次枚举当前最大d值,再枚举c如果找到,就可以了。找不到就no 我的hash有毛病,刚学,希望指导下。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int len1 = 3214567, len2 = 642913;
int pool[10000], poolen, hash[len1], left[len1], right[len1], pleft[10000], pright[10000], in[1001], temp;
int h1(int a){
return a % len1;
}
int h2(int a){
temp = a % len2;
return temp;
}
int h(int a, int i){
return (h1(a) + i * h2(a)) % len1;
}
void insert(int v, int l, int r){
int i, k;
for(i = 0; i <= 5; i++){
k = h(v, i);
if(hash[k] == -1){
hash[k] = v;left[k] = l;right[k] = r;
return;
}
}
pool[poolen] = v;
pleft[poolen] = l;
pright[poolen++] = r;
}
bool search(int v, int v1, int v2){
int i, k;
for(i = 0; i <= temp; i++){
k = h(v, i);
if(hash[k] == v){
if(in[left[k]] == v1 || in[left[k]] == v2 || in[right[k]] == v1 || in[right[k]] == v2)continue;
if(in[left[k]] + in[right[k]] == v1 - v2)return true;
}
else if(hash[k] == -1)return false;
}
for(i = 0; i < poolen; i++)if(pool[i] == v){
if(in[pleft[i]] == v1 || in[pleft[i]] == v2 || in[pright[i]] == v1 || in[pright[i]] == v2)continue;
if(in[pleft[i]] + in[pright[i]] == v1 - v2)
return true;
}
return false;
}
bool cmp(int a, int b){
return a < b;
}
int jdz(int a){return a > 0 ? a : -a;}
int main(){
freopen("2549.in", "r", stdin);
freopen("2549.out", "w", stdout);
int n, i, j, res, t, len, d, ans, tin[1001];
bool orz;
while(scanf("%d", &n), n){
len = 0;ans = -0x7fffffff;
memset(hash, -1, sizeof(hash));
for(i = 0; i < n; i++){
scanf("%d", &t);
tin[len] = t;in[len++] = t;
}
for(i = 0; i < len; i++){
for(j = i + 1; j < len; j++)
insert(jdz(in[i] + in[j]), i, j);
}orz = false;
make_heap(tin, tin + len, cmp);
for(i = 0, t = len; i < len; i++, t--){
for(j = 0; j < len; j++){
if(tin[0] != in[j] && search(jdz(tin[0] - in[j]), tin[0], in[j])){
orz = true;ans = tin[0];
break;
}
}
if(orz)break;
pop_heap(tin, tin + t, cmp);
}
if(!orz)puts("no solution");
else printf("%d\n", ans);
}
return 0;
}