[HDU 4666]Hyperspace[最远曼哈顿距离][STL]-白红宇

[HDU 4666]Hyperspace[最远曼哈顿距离][STL]

阅读量：6138 次

发布时间：2019-06-21

本文共 2755 字，大约阅读时间需要 9 分钟。

题意:

许多 k 维点, 求这些点之间的最远曼哈顿距离. 并且有 q 次操作, 插入一个点或者删除一个点. 每次操作之后均输出结果.

思路:

用"疑似绝对值"的思想, 维护每种状态下各点的计算值, 插入或删除一个点就更新一次每种状态(用 multiset 或 map 或 priority_queue 实现), 每次求ans时扫一遍最大差值即可.

为了练习STL, 每一个都实现一次.

multiset

/* **********************************************Author      : kuangbinCreated Time: 2013/8/13 18:25:38File Name   : F:\2013ACM练习\2013多校7\1001.cpp*********************************************** *///4640MS    14972K#include 
    
     #include 
     
      #include 
      
       using namespace std;int a[60010][10];multiset
       
        mst[1<<5];int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    int q,k;    while(scanf("%d%d",&q,&k)==2)    {        for(int i = 0;i < (1<
        
         <= q;i++)        {            scanf("%d",&od);            if(od == 0)            {                for(int j = 0;j < k;j++)                    scanf("%d",&a[i][j]);                for(int j = 0; j < (1<

::iterator it = mst[j].find(s); mst[j].erase(it); } } int ans = 0; for(int j = 0; j < (1<

::iterator it = mst[j].end(); it--; int t1 = (*it); it = mst[j].begin(); int t2 = (*it);//用于作差 ans = max(ans,t1-t2);//保留最大值 } printf("%d\n",ans); } } return 0;}

map

//8359MS	37928K慢死了#include 
    
     #include 
     
      #include 
      using namespace std;int a[60010][6];map
       
         mp[1<<5];int main(){    int q,k;    while(scanf("%d %d",&q,&k)==2)    {        for(int i=0;i<1<
        
         ::iterator it = mp[s].find(t);                    mp[s][t]--;                }            }            int ans = 0;            for(int s=0;s<(1<
         
          ::iterator it = mp[s].end(); it--; while(it->second==0) it--; int mx = it->first;///first~~~ it = mp[s].begin(); while(it->second==0) it++; int mi = it->first; ans = max(ans, mx - mi); // printf("mx = %d, mi = %d\n",mx,mi); } printf("%d\n",ans); } }}

priority_queue

优先队列只能返回队首元素,因此需要两个队列分别求最大最小值.

对于已删除的元素, 无法直接删除, 可以做标记, 碰到已删除的元素时直接pop掉就行了.

因此入队的就不能仅仅是一个值(前两个有find功能, 不需要额外标号), 而应该是一个记录key和value的结构体.

//2218MS	36748K#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int a[6];bool vis[60005];typedef struct ascending_node{    int id,t;    bool operator<(const ascending_node& a) const    {        return t > a.t;    }}anode;typedef struct descending_node{    int id,t;    bool operator<(const descending_node& a) const    {        return t < a.t;    }}dnode;/*  2812MS	  30224Kpriority_queue
        
          apq[1<<5];priority_queue
         
           dpq[1<<5];int main(){ int q,k; while(scanf("%d %d",&q,&k)==2) { for(int i=0;i<1<
          
            apq[1<<5]; priority_queue
           
             dpq[1<<5];/**/ anode t1; dnode t2; memset(vis,false,sizeof(vis)); int od, x; for(int i=1;i<=q;i++) { scanf("%d",&od); if(!od) { for(int j=0;j

转载地址：http://bgkya.baihongyu.com/