学步园

题目连接：点击打开链接

这道题就是没有过的那道，栈的应用吧。一开始，我的思路的错的。

一开始做这到题就是想的很是简单，都没有怎么想，直接就去写，很是理所应当的WA了好多次，这就我所说的算法的合法性。一定要验证算法的合理性。

附上WA代码，以此为戒。

 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

const int N=105;

bool cmp(int a,int b)
{
    if(a>b) return true;
    return false;
}

int main()
{
    char a[N];
    while(cin>>a)
    {
        getchar();
        char b[N];
        int len=strlen(a),p=0;
        strcpy(b,a);
        sort(b,b+len,cmp);
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<len;j++)
            if(a[j]==b[i]&&j>=p)
            {printf("%c",a[j]);a[j]='#';p=j;}
        }
        for(int i=len-1;i>=0;i--)
            if(a[i]!='#') printf("%c",a[i]);
        printf("\n");
    }
    return 0;
}
        

思路就是直接从最大数来，次小的看是否在其右侧，右侧就为下一位。这种思路错在次小的在左边也可以的。

看了题解，按照题解的思路来的。

imax[i]数组来存储i-n之间的最大数，判断栈顶元素的是否是大于其后面所有元素的最大值，若大于就出栈，否则，入栈。

 
#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b

const int N=100;

int main()
{
    char s[N];
    while(~scanf("%s",s))
    {
        int l=strlen(s),imax[N],Imax=0;
        for(int i=l-1;i>=0;i--)
        {
            imax[i]=max(Imax,s[i]);
            Imax=imax[i];
        }
        int stack[N],top=0;
        stack[0]=-1;
        stack[++top]=s[0];
        for(int i=1;i<l;i++)
        {
            if(stack[top]>=imax[i]) {printf("%c",stack[top--]);i--;}
            else stack[++top]=s[i];
        }
        for(int i=top;i>=1;i--)
        printf("%c",stack[i]);
        printf("\n");
    }
}
        

这是正确的代码，由这题可以看错，自己的思路又出问题了，没有考虑左边的情况。

也可以看出，搞ACm需要很严密的思路。考虑问题要全面。