HDU 5818 Joint Stacks

Aug 10, 2016 | Algorithm | 阅读

文章目录

HDU_5818
思路
AC代码

HDU_5818

思路

Joint Stacks
比较简单巧妙的一个做法是引入一个新的栈C，每次合并的时候就把A和B合并到C上，然后把A和B都清空. push还是按正常做，pop注意当遇到要pop的栈为空时，因为题目保证不会对空栈进行pop操作，所以这时应直接改为对C栈进行pop操作. 这样做因为保证每个元素最多只在一次合并中被处理到，pop和push操作当然也是每个元素只做一次，所以总复杂度是O(N)的. 另一种做法是用链表来直接模拟，复杂度也是O(N)，但代码量稍大一些.

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define NV 100005
int aind,bind,C[2*NV],cind,pre;
struct mystly
{
    int value,time;
}A[NV],B[NV];
bool ok[NV];
int main(){
    int n,tmp,ca=0;char str[4];
/*    freopen("1010.in","r",stdin);
    freopen("myout.out","w",stdout);*/
    while(scanf("%d",&n)){
        if(n==0)break;
        printf("Case #%d:\n",++ca);
        aind=0,bind=0,cind=0;
        for(int i=1 ;i<=n ;i++){
            scanf("%s",str);
            if(str[1]=='u'){
                scanf("%s%d",str,&tmp);
                if(str[0]=='A'){
                    A[++aind].time=i;
                    A[aind].value=tmp;
                }
                else{
                    B[++bind].time=i;
                    B[bind].value=tmp;
                }
            }
            else if(str[1]=='o'){   
                scanf("%s",str);
                if(str[0]=='A'){
                    if(aind>0){
                        printf("%d\n",A[aind--].value);
                    }
                    else{
                        printf("%d\n",C[cind--]);
                    }
                }
                else{
                    if(bind>0){
                        printf("%d\n",B[bind--].value);
                    }
                    else{
                        printf("%d\n",C[cind--]);
                    }
                }
            }
            else if(str[1]=='e'){
                scanf("%s%s",str,str);
                int ii=1,jj=1;
                while(ii<=aind && jj<=bind){
                    if(A[ii].time<B[jj].time){
                        C[++cind]=A[ii++].value;
                    }
                    else{
                        C[++cind]=B[jj++].value;
                    }
                }
                while(ii<=aind)C[++cind]=A[ii++].value;
                while(jj<=bind)C[++cind]=B[jj++].value;
                aind=0;bind=0;
            }
        }
    }
    return 0;
}

ACM