PIPIOJ 1061: PIPI的目标Ⅵ 枚举

题目：

http://39.106.164.46/problem.php?id=1061

思路：

由于题目要求最后按照字典序输出，我们可以先对数组排个序，然后从头枚举a，然后枚举b，为了降低复杂度，枚举c和d的时候可以采取折半枚举，用两个指针l和r指向左右两端，判断c+d是否等于t-(a+b)，若相等，则记录一个结果。注意最后我们还要筛去重复的记录。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,t,a[MAX];

struct node{
    int a,b,c,d;
    node(int aa,int bb,int cc,int dd){
        a=aa,b=bb,c=cc,d=dd;
    }
};

bool cmp(node x,node y){
    if(x.a==y.a){
        if(x.b==y.b){
            if(x.c==y.c) return x.d<y.d;
            else return x.c<y.c;
        }else{
            return x.b<y.b;
        }
    }else{
        return x.a<y.a;
    }
}

int main(){
    while(cin>>n>>t){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        vector<node> vec;
        sort(a,a+n);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int sum=t-(a[i]+a[j]);
                int l=j+1,r=n-1;
                while(l<r){
                    int tmp=a[l]+a[r];
                    if(tmp==sum){
                        vec.push_back(node(a[i],a[j],a[l],a[r]));
                    }
                    if(tmp>sum) r--;
                    else l++;
                }
            }
        }
        sort(vec.begin(),vec.end(),cmp);
        int len=vec.size();
        for(int i=0;i<len;i++){
            if(i==len-1||(vec[i].a!=vec[i+1].a||vec[i].b!=vec[i+1].b||vec[i].c!=vec[i+1].c||vec[i].d!=vec[i+1].d)){
                printf("%d %d %d %d\n",vec[i].a,vec[i].b,vec[i].c,vec[i].d);
            }
        }
    }
    return 0;
}