首页 > 代码库 > HDU 4666

HDU 4666

2024-08-05 08:09:42   213人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4666

求m维最远曼哈顿距离

借鉴别人的思路http://www.cnblogs.com/jackge/archive/2013/08/14/3256402.html

以二维平面为例：

设距离最远的两点为 i, j，可知所求的最大距离必定有以下四种形式之一：

(xi-xj)+(yi-yj), (xj-xi)+(yi-yj), (xi-xj)+(yj-yi), (xj-xi)+(yj-yi) 变形一下，把相同点的坐标放到一起，

即 (xi+yi)-(xj+yj), (-xi+yi)-(-xj+yj), (xi-yi)-(xj-yj), (-xi-yi)-(-xj-yj)，可以发现即去绝对值之后把同一点的坐标放在一起，对应坐标符号相同。

假如我们用0表示符号，用1表示正号，那么 (xi+yi) 可以表示为 11。

 

由于在线并且有删除操作，最大最小值我们分别用两个堆来维护，枚举所有状态找出最大值即可

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;struct node1{    int v,num;    friend bool operator <(node1 a,node1 b){        return a.v<b.v;    }};struct node2{    int v,num;    friend bool operator <(node2 a,node2 b){        return a.v>b.v;    }    };int vis[60006];int main(){    int q,m;    while(~scanf("%d%d",&q,&m)){        priority_queue <node1> h1[1<<5];        priority_queue <node2> h2[1<<5];        memset(vis,0,sizeof(vis));        for(int i=1;i<=q;i++){            int op;            scanf("%d",&op);            int a[6];            if(!op){                for(int j=0;j<m;j++)                    scanf("%d",&a[j]);                for(int j=0;j<(1<<m);j++){                    int cnt=0;                    for(int k=0;k<m;k++){                        if(j&(1<<k)){                            cnt+=a[k];                        }                        else{                            cnt-=a[k];                        }                    }                    node1 p1;                    node2 p2;                    p1.v=p2.v=cnt;                    p1.num=i;p2.num=i;                    h1[j].push(p1);                    h2[j].push(p2);                }            }            else{                int x;                scanf("%d",&x);                vis[x]=1;            }            int ans=0;            for(int j=0;j<(1<<m);j++){                node1 cnt1;                node2 cnt2;                int flag=0;                while(!h1[j].empty()){                    cnt1=h1[j].top();                    if(!vis[cnt1.num]){                        flag++;                        break;                    }                    h1[j].pop();                }                while(!h2[j].empty()){                    cnt2=h2[j].top();                    if(!vis[cnt2.num]){                        flag++;                        break;                    }                    h2[j].pop();                }                if(flag==2)ans=max(ans,cnt1.v-cnt2.v);            }            printf("%d\n",ans);        }    }    return 0;}
View Code

 

HDU 4666


联系
我们