hdu1022 - Train Problem I

曾经终败给现在 2022-07-13 08:08 54阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1022][http_acm.hdu.edu.cn_showproblem.php_pid_1022]

# 定位 #

*  数据结构

# 分析 #

*  火车进站，典型的栈问题。
    
    栈的特点是后入先出，即实现逆序。
 *  火车进站：栈顶不在出站次序时，压栈。注意，空栈要特殊处理。
 *  火车出站：栈顶对应出站次序时，出栈。
 *  失败：进站操作完成，出站操作卡死(栈顶无法出栈)。

# 代码 #

#include <iostream>
    #include <cstdio>
    #include <stack>
    
    using namespace std;
    
    int main()
    {
        int n;
        while(scanf("%d",&n) != EOF)
        {
            int i = 0;  //s1[i]
            int j = 0;  //s2[j]
            int k = 0;  //path[k]
            stack<char> st;
            char *s1 = new char[n];
            char *s2 = new char[n];
            int *path = new int[2*n];
            scanf("%s",s1);
            scanf("%s",s2);
            while(j < n)
            {
                if((st.empty() || st.top() != s2[j]) && (i < n))
                {
                    st.push(s1[i]);
                    path[k] = 1;
                    i++;
                    k++;
                }
                else
                {
                    if(st.top() == s2[j])
                    {
                        st.pop();
                        path[k] = 0;
                        j++;
                        k++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            if(st.empty())
            {
                printf("Yes.\n");
                for(int kk=0;kk<k;kk++)
                {
                    if(path[kk] == 1)
                    {
                        printf("in\n");
                    }
                    else
                    {
                        printf("out\n");
                    }
                }
                printf("FINISH\n");
            }
            else
            {
                printf("No.\nFINISH\n");
            }
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">15MS</td> 
   <td align="center">1740K</td> 
   <td align="center">1474B</td> 
   <td align="center">c++</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

## 过程模拟 ##

以`15423`为例，手动模拟一遍算法流程。

## 直接驶过情况的处理 ##

对于火车无需进栈，而是直接驶过的情况，最好也进行入栈处理。这样可以简化进出站逻辑，进站就压栈，只从栈顶出站，即`st.top() == s2[j]`。

Thanks everyone!

[http_acm.hdu.edu.cn_showproblem.php_pid_1022]: http://acm.hdu.edu.cn/showproblem.php?pid=1022