HDU4666+POJ2926[最遠曼哈頓距離]

一開始就明白那個N*1《k的算法了，

可無奈刪除操作耗時還是太多，最後學習了STL set,map相應的用法，方便好多。

STL真的是一個好工具

#include<iostream>   
#include<cstdio>   
#include<map>   
#include<set>   
#include<vector>   
#include<cstring>   
using namespace std;  
multiset<int> a[60005];  
int x[60005][6];  
int main()  
{  
  int n,k,op,num;  
  while(scanf("%d%d",&n,&k)!=EOF)  
  {  
      for(int i=0;i<1<<k;i++)  
        a[i].clear();  
      for(int i=1;i<=n;i++)  
      {  
          scanf("%d",&op);  
          if(op==0)  
          {  
              for(int j=0;j<k;j++)  
                scanf("%d",&x[i][j]);  
              for(int j=0;j<1<<k;j++)  
              {  
                 int s=0;  
                 for(int q=0;q<k;q++)  
                 {  
                     if(j&1<<q) s+=x[i][q];  
                     else s-=x[i][q];  
                 }  
                 a[j].insert(s);  
              }  
          }  
          else  
          {  
              scanf("%d",&num);  
              for(int j=0;j<1<<k;j++)  
              {  
                  int s=0;  
                  for(int q=0;q<k;q++)  
                  {  
                      if(j&1<<q) s+=x[num][q];  
                      else s-=x[num][q];  
                  }  
                  multiset<int>::iterator sum=a[j].find(s);  
                  a[j].erase(sum);  
              }  
          }  
          int ans=-100000000;  
          for(int j=0;j<1<<k;j++)  
          {  
              multiset<int>::iterator t=a[j].end();  
              t--;  
              int t1=(*t);  
              t=a[j].begin();  
              int t2=(*t);  
              ans=max(ans,t1-t2);  
          }  
          printf("%d\n",ans);  
      }  
  }  
  return 0;  
}