hdu 4666:Hyperspace（最远曼哈顿距离 + STL使用）

Hyperspace

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1023    Accepted Submission(s): 492

Problem Description

The great Mr.Smith has invented a hyperspace particle generator. The device is very powerful. The device can generate a hyperspace. In the hyperspace, particle may appear and disappear randomly. At the same time a great amount of energy was generated.
However, the device is in test phase, often in a unstable state. Mr.Smith worried that it may cause an explosion while testing it. The energy of the device is related to the maximum manhattan distance among particle.
Particles may appear and disappear any time. Mr.Smith wants to know the maxmium manhattan distance among particles when particle appears or disappears.

 

Input

The input contains several test cases, terminated by EOF.
In each case: In the first line, there are two integer q(number of particle appear and disappear event, ≤60000) and k(dimensions of the hyperspace that the hyperspace the device generated, ≤5). Then follows q lines. In each line, the first integer ‘od’ represents the event: od = 0 means this is an appear
event. Then follows k integer(with absolute value less then 4 × 10⁷). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.

 

Output

Each test case should contains q lines. Each line contains a integer represents the maximum manhattan distance among paticles.

 

Sample Input

  -

  -
  -

 -
  -

Sample Output

746

1456

1456

1456

2512

5571

8922

 

Source

2013 Multi-University Training Contest 7

 

Recommend

zhuyuanchen520   |   We have carefully selected several similar problems for you:  4822 4821 4820 4819 4818 

---

 

　　最远曼哈顿距离 + STL库使用。

　　题意是已知q和n，q是请求的数量，n是平面点的维数。接下来输入q行请求，每行请求由2部分组成，分别是指令od和操作数，od=0代表加入点，od1代表删除点。如果od=0，后面会有n个整数，代表n维点的n个坐标值；如果od=1，代表删除点，删除的是第q条指令加入的点，而不是删除当前已有的第几个点。例如指令“1 5”，表示删除第5行的指令加入的点。

　　不清楚最远曼哈顿距离怎么求的筒靴可以看这里：最远曼哈顿距离

　　其实就是将绝对值去掉，移位，然后发现规律。多找几组例子对照着演算一下就容易明白了。

　　明白基本原理了可以先看看一道最远曼哈顿距离的入门题：poj 2926:Requirements（最远曼哈顿距离，入门题）

　　因为有删除操作，所以直接用数组会比较麻烦，这时候用STL中的映射表map和集合set就比较方便了。本来只想找一道类似的题，直接套我写的模板过的，结果找到这么一道还得用STL的题，表示很无奈，借机熟悉熟悉STL吧。好吧我承认我是参照着别人的代码才写出来。

　　参考博客：HDU 4666 Hyperspace

　　代码：

 #include <iostream>
 #include <iomanip>
 #include <stdio.h>
 #include <map>
 #include <set>
 using namespace std;
 int main()
 {
     int i,j,k,q,dem;
     while(scanf("%d%d",&q,&dem)!=EOF){
         multiset <int> s[];    //定义多重集合
         multiset <int>::iterator it1,it2;
         map <int,int> m[];    //式子对点
         int a[];
         for(i=;i<=q;i++){
             int od;
             scanf("%d",&od);
             if(od==){    //添加操作
                 for(j=;j<dem;j++)
                     scanf("%d",&a[j]);
                 for(j=;j<(<<(dem-));j++){    //用二进制形式遍历所有可能的运算情况
                     int sum = ;
                     for(k=;k<;k++){    //因为是五维的，所以有4个运算符
                         //提取当前运算符
                         int t = j & <<k;    //1为+，0为-
                         if(t) sum+=a[k];
                         else sum-=a[k];
                     }
                     s[j].insert(sum);
                     m[j][i] = sum;
                 }
             }
             else{    //删除
                 int t;
                 scanf("%d",&t);
                 for(j=;j<(<<(dem-));j++){
                     if(m[j].size()>){
                         s[j].erase(s[j].find(m[j][t]));
                         m[j].erase(t);
                     }
                 }
             }
             int Max = ;
             for(j=;j<(<<(dem-));j++){
                 if(s[j].size()>){
                     it1 = s[j].begin();
                     it2 = s[j].end();
                     it2--;
                     Max = *it2-*it1 > Max? *it2-*it1 : Max;
                 }
             }
             printf("%d\n",Max);
         }
     }
     return ;
 }

Freecode : www.cnblogs.com/yym2013