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