Hyperspace
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 987 Accepted Submission(s): 476
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.
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 7). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.
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 7). 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
10 2 0 208 403 0 371 -180 1 2 0 1069 -192 0 418 -525 1 5 1 1 0 2754 635 0 -2491 961 0 2954 -2516
Sample Output
0 746 0 1456 1456 1456 0 2512 5571 8922
Source
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you: 4812 4811 4810 4809 4808
本题要求最大哈夫曼距离。k维空间的哈夫曼距离为∑|xi0-xi1|.任意维数的空间（x0,x1,…xk）,每维的坐标有2^k组合，任意两个点的对应组合相减，取最大值就是最大哈夫曼距离。就是要维护一个优先级队列或者堆（此题用multiset容器）。
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
struct cmp
{
bool operator()(const int a,const int b)
{
return a<b;
}
};
const int MAXN=(1<<5)+10;
multiset<int,cmp>MyMulSet[MAXN];
int Point[60000+100][MAXN];
int del[60000+100][MAXN];
int main()
{
int q,k,op;
while(~scanf("%d%d",&q,&k))
{
for(int i=0;i<MAXN;i++)
MyMulSet[i].clear();
int cnt=1<<k;
int row=0;
while(row<q)
{
scanf("%d",&op);
if(0==op)
{
for(int i=0;i<k;i++)
scanf("%d",&Point[row][i]);
for(int i=0;i<cnt;i++)
{
int ele=0;
for(int j=0;j<k;j++)
{
if(i&(1<<j))
ele+=Point[row][j];
else ele-=Point[row][j];
}
del[row][i]=ele;
MyMulSet[i].insert(ele);
}
}
else if(1==op)
{
int id;
scanf("%d",&id);
id--;
for(int i=0;i<cnt;i++)
{
multiset<int>::iterator iter=MyMulSet[i].find(del[id][i]);
if(iter!=MyMulSet[i].end())
MyMulSet[i].erase(iter);
}
}
int ans=0;
for(int i=0;i<cnt;i++)
{
if(MyMulSet[i].size()>1)
{
multiset<int>::iterator En=MyMulSet[i].end();
--En;
multiset<int>::iterator St=MyMulSet[i].begin();
ans=max(ans,(*En)-(*St));
}
}
printf("%d\n",ans);
row++;
}
}
return 0;
}