poj 2549 折半枚举

传送门：https://vjudge.net/problem/POJ-2549

题意：给你一个整数的集合，要求在集合里面选择四个数a,b,c,d满足a+b+c=d，在这前提下d最大。没有满足等式的输出no solution

这题是从《挑战程序设计竞赛》来的。最近状态很糟糕，这是最近鲜有的1A。

首先n是1000，可以想到n²或者n²logn的做法。我们可以把等式写成a+b=d-c。然后先用n²预处理出a+b的数列。然后用n²枚举d-c，再用logn在a+b找看看有没有等于d-c的。就搞定啦。

// Cease to struggle and you cease to live
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
#define pii pair<ll,int> 
ll num[1000+9];
pii ab[(int)1e6+9];
int main() {
    int n;
    while(~scanf("%d",&n)){
        if(!n) break;
        int nab=0;
        for(int i=1;i<=n;++i) scanf("%lld",&num[i]);
        sort(num+1,num+1+n);
        for(int i=1;i<n;++i){
            for(int j=i+1;j<=n;++j){
                ab[++nab]=make_pair(num[i]+num[j],num[i]);
            }
        }
        sort(ab+1,ab+1+nab);
        bool ok=0;
        for(int i=n;i>1 && ok==0;--i){
            for(int j=i-1;j>=1 && ok==0;--j){
                int p=lower_bound(ab+1,ab+1+nab,make_pair(num[i]-num[j],-0x3f3f3f3f))-ab;
                if(p==1+nab) continue;
                if(ab[p].first!=num[i]-num[j]) continue;
                ll a=ab[p].second,b=ab[p].first-a;
                if(a==num[i] || a==num[j] || b==num[i] || b==num[j]) continue;
                ok=1;
                printf("%lld\n",num[i]);
            }
        }
        if(!ok) puts("no solution");
    }
    return 0;
}