POJ 2549 二分+HASH

题目链接:http://poj.org/problem?id=2002

题意:给定一个n个数字组成的序列,然后求出4个数使得a+b+c=d,求d的最大值。其中a,b,c,d要求是给定序列的数,并且不能重复拿同一个位置的数。

思路:先处理a+b,把a+b的组合和在序列的位置存起来。然后枚举d,c计算d-c时候在a+b中出现过。并且a.b.c.d在序列的位置都不同。注意结果可能爆int。

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long int LL;
typedef unsigned int uint;
#define mp(x,y) make_pair(x,y)
#define INF 536870920
const int MAXN=+;
struct Node{
int idx,idy;
LL val;
}Hash[MAXN*MAXN];
LL num[MAXN];int cnt;
bool cmp(Node a,Node b){
return a.val<b.val;
}
bool search(LL V,int x,int y){
int L=,R=cnt-,Mid;
while(R>=L){
Mid=(L+R)/;
if(Hash[Mid].val>=V){
R=Mid-;
}
else{
L=Mid+;
}
}
for(int i=L;Hash[i].val==V;i++){
if((Hash[i].idx!=x&&Hash[i].idy!=y)&&(Hash[i].idx!=y&&Hash[i].idy!=x)){
return true;
}
}
return false;
}
int main(){
#ifdef kirito
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int n;
while(scanf("%d",&n)&&n){
LL ans=-INF; cnt=;
for(int i=;i<n;i++){
scanf("%I64d",&num[i]);
}
for(int i=;i<n;i++){
for(int j=i+;j<n;j++){ //make a+b
Hash[cnt].idx=i; Hash[cnt].idy=j;
Hash[cnt++].val=num[i]+num[j];
}
}
sort(Hash,Hash+cnt,cmp);
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(i==j){
continue;
}
LL V=num[i]-num[j]; //d-c
if(search(V,i,j)){ //d-c in a+b ?
ans=max(ans,num[i]);
}
}
}
if(ans==-INF){
printf("no solution\n");
}
else{
printf("%I64d\n",ans);
}
}
return ;
}
上一篇:C#中语音合成简单使用


下一篇:mysql,命令导入\导出表结构或数据