【题目链接】 http://poj.org/problem?id=2549

【题目大意】

  给出一个数集,从中选择四个元素,使得a+b+c=d,最小化d

【题解】

  我们对a+b建立Hash_table,之后枚举c和d,寻找c-d且不由c和d构成的hash值是否存在
  如果存在,那么d就可以用来更新答案

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
const int N=1024,mod=1<<18;
int n,x[N],head[mod],cnt;
struct data{int a,b,sum,nxt;}g[N*N];
inline int hash(int x){return abs(x)&(mod-1);}
void insert(int a,int b,int sum){
int key=hash(sum);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].sum==sum&&g[i].a==a&&g[i].b==b)return;
}g[cnt].a=a;g[cnt].b=b;g[cnt].sum=sum;
g[cnt].nxt=head[key]; head[key]=cnt++;
}
bool search(int a,int b,int sum){
int key=hash(sum);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].sum!=sum||g[i].a==a||g[i].a==b||g[i].b==a||g[i].b==b)continue;
return 1;
}return 0;
}
void init(){cnt=0;memset(head,-1,sizeof(head));}
int main(){
while(scanf("%d",&n)&&n){
init();
for(int i=0;i<n;i++)scanf("%d",&x[i]);
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)insert(i,j,x[i]+x[j]);
int flag=0,ans=INT_MIN;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(i==j)continue;
if(search(i,j,x[i]-x[j])){
flag=1;ans=max(ans,x[i]);break;
}
}if(flag)printf("%d\n",ans);
else puts("no solution");
}return 0;
}

最新文章

  1. 用WebRequest +HtmlAgilityPack 从外网抓取数据到本地
  2. MyEclipse 2014(激活)
  3. &lt;script&gt;中的代码
  4. Unity3D热更新全书-脚本(五) NGUI
  5. JMeter2.13进行压力测试
  6. Web Service实现分布式服务的基本原理
  7. 怎样用VB自动更新应用程序
  8. HP QC(Quality Center)在Windows 7 IE8 IE9下不能工作解决方案
  9. PHP学习笔记1-常量,函数
  10. kvm与qemu
  11. Linux shell 操作 postgresql,并设置crontab任务
  12. 命名空间“Microsoft”中不存在类型或命名空间名称“Office”(是缺少程序集引用吗?)
  13. 1、在eclipse中导入Java的jar包方法---JDBC【图文说明】
  14. 想玩 BGP 路由器么?用 CentOS 做一个
  15. 使用百度地图开发一个导航定位demo-android学习之旅(77)
  16. Spring Boot 入门教程 | 图文讲解
  17. 爬虫(七)图片懒加载技术、selenium和PhantomJS
  18. ADB驱动
  19. iOS获取当前城市
  20. mybatis教程4(动态SQL)

热门文章

  1. selenium初识(一)
  2. java细节篇(==和equals的区别)
  3. android DOM解析Xml
  4. quagga源码学习--BGP协议中的routemap
  5. Java性能监控之Java程序执行解析
  6. CSLM 配置粗解
  7. IE8专用hack
  8. 湘潭邀请赛 2018 I Longest Increasing Subsequence
  9. 安装PL/SQL Developer,链接本地64位Oracle
  10. rest项目的基础返回类设计