MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
求解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, 
-1sizeof(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;
}

posted on 2009-10-03 02:05 memorygarden 阅读(628) 评论(0)  编辑 收藏 引用 所属分类: 报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理