hdu4666 最远曼哈顿距离

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4666

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
const int maxn = 60060;

struct MaxHeap{
    int d;                      //k维的各种加或减的和；
    int p;                      //每个坐标和所属的标号
    MaxHeap(int d=0,int p=0):d(d),p(p) {}
    bool operator < (const MaxHeap& r) const{
        return d < r.d;
    }
};   
struct MinHeap{
    int d;
    int p;
    MinHeap(int d=0,int p=0):d(d),p(p) {}
    bool operator < (const MinHeap& r) const{
        return d > r.d;
    }
};
priority_queue<MaxHeap> Max[32];  //存储1<<k种坐标组合情况；
priority_queue<MinHeap> Min[32];
int q,k;
bool del[maxn];          //标记别删除的点；

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);
    while(cin>>q>>k){
        memset(del,0,sizeof(del));
        for(int i=0;i<32;i++){
            while(!Max[i].empty())   Max[i].pop();
            while(!Min[i].empty())   Min[i].pop();
        }
        int a[6],od;
        MaxHeap temp1;     MinHeap temp2;
        for(int m=1;m<=q;m++){
            scanf("%d",&od);
            if(od == 0){
                for(int i=0;i<k;i++)  scanf("%d",&a[i]);
                for(int i=0;i<(1<<k);i++){
                    int add = 0;
                    for(int j=0;j<k;j++)
                        if(1<<j & i)  add += a[j];
                        else          add -= a[j];
                    temp1 = MaxHeap(add,m); 
                    temp2 = MinHeap(add,m);
                    Max[i].push(temp1);
                    Min[i].push(temp2);
                }
            }
            else{
                int id;
                scanf("%d",&id);
                del[id] = true;
            }
            /*****   统计答案   ******/
            int ans = 0;
            for(int i=0;i<(1<<k);i++){
                if(!Max[i].empty())  temp1 = Max[i].top();    //下面从最大堆中取没被删除的最大；
                while(!Max[i].empty() && del[temp1.p]){
                    Max[i].pop();
                    temp1 = Max[i].top();
                }
                if( Max[i].empty()){     //最大堆为空，没temp1没取到元素；直接退出。
                    ans = 0; break;
                }
                if(!Min[i].empty())  temp2 = Min[i].top();    //下面从最小堆中取没被删除的最小；
                while(!Min[i].empty() && del[temp2.p]){
                    Min[i].pop();
                    temp2 = Min[i].top();
                }
                if( Min[i].empty()){    //最小堆为空，没temp2没取到元素；
                    ans = 0; break;
                }
                ans = max(ans,temp1.d-temp2.d);
            }
            printf("%d
",ans);
        }
    }
}