题目链接：HDU4666
题目大意：给你 q个事件，在k维空间，每个事件会出现一个点或者消失一个点，出现一个点会给出该点在k维空间下的坐标，消失一个点会给出消失的点是在哪个事件中出现的，求每次事件中最大的Manhattan距离（曼哈顿距离）。
代码参考：大佬的代码 我在原代码的基础上加上了一些注释，便于大家理解
知识点：
1、曼哈顿距离？
闵可夫斯基距离(Minkowsk distance)-MinkowskiDistanceMeasure（默认p=3）
可看成是欧氏距离的指数推广，还没有见到过很好的应用实例，但通常，推广都是一种进步，特别的，
当p=1,也成做曼哈顿距离，也称绝对距离，曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果。ManhattanDistanceMeasure.
2、
以二维平面为例：
设距离最远的两点为 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)，
可以发现即去绝对值之后把同一点的坐标放在一起，对应坐标符号相同。这句话多理解几遍！
举个例子就很清楚了， 比如 （10，-2） （-2,10） 其Manhattan距离为24，那我们来看看这个是怎么算出来的。
10 - （-2）+|-2-10|=24 实质为 10-(-2)+2-(-10)
在这道题中，我们把每个坐标的所有正负情况枚举，也就是2^k种情况，
比如二维平面，x1=10 y1=-2 那么有2^2=4种形式 （x1,y1） （-x1,y1） （x1,-y1 ）（-x1,-y1） ，
正正10-2=8 负正-10-2=-12 正负10-（-2）=12 负负-10-(-2)=-8
对应的(-2,10)同样有4种情况，正正-2 +10=8 负正2+10=12 正负-2-10=-12 负负2-10=-8
又因为上面得出的结论，最大值对应坐标符号相同，所以我们可以用每种情况的最大值减去最小值即可得出最大值 12-（-12）=24.
说白了，就是让我们计算这两点之间的距离 (10,-2) (-2,10) 代码化，我们直观就可以看出 距离为 10-(-2)+10-(-2) 代码实现就是找到 正负这种情况，相减。
我说了这么多，就是为了解释这句话，对应坐标符号相同。如果这句话懂了，那么这题你也搞明白了。
3、另外在这道题中，学习了multiset的应用，首先集合中可以有重复的元素，元素会按照从小到大排序，可以用find()去找某个元素的值，insert()增加,erase()删除，遍历的时候用迭代器 iterator，end()指向最后一个元素后一位。取值用*it
AC代码：
/* HDU4666 2017年8月6日08:18:38 手敲一遍 multiset 的应用 AC */ #include<stdio.h> #include<set> #include<algorithm> using namespace std; const int maxn=60000+10; int n,m,num[maxn][10]; multiset<int> mst[1<<5]; multiset<int>::iterator it1,it2; int main(){ while(~scanf("%d%d",&n,&m)){ /*每次循环将多重集清空*/ for(int i=0;i<(1<<5);i++){ mst[i].clear(); } int od,x; for(int i=1;i<=n;i++){ scanf("%d",&od); if(od==0){ for(int j=0;j<m;j++){ scanf("%d",&num[i][j]); } /*如果是m维度 那么每个坐标对应 2^m种组合 0-2^m-1 比如二维 a,b 对应4种组合 a b a -b -a b -a -b */ for(int j=0;j<(1<<m);j++){ int sum=0; for(int k=0;k<m;k++){ //这个比较难理解 if(j&(1<<k)) sum+=num[i][k]; else sum-=num[i][k]; } mst[j].insert(sum); } } else{ scanf("%d",&x); for(int j=0;j<(1<<m);j++){ int sum=0; for(int k=0;k<m;k++){ if(j&(1<<k)) sum+=num[x][k]; else sum-=num[x][k]; } it1=mst[j].find(sum); mst[j].erase(it1); } } int ans=0; for(int j=0;j<(1<<m);j++){ it1=mst[j].end(); it1--;//因为end指向最后一个数据的后一位，所以往后挪一位。 it2=mst[j].begin(); ans=max(ans,*it1-*it2); } printf("%d\n",ans); } } return 0; }
