codeforces 797c minimal string

2017-08-01 21:49:34

writer：pprp

集训第一天

题意如下：

• Codeforces 797C Minimal string
• 给定长度为n的小写字母字符串s，及空串t, u，两种操作
• 1. 将s的第一个字符加到t的末尾
• 2. 将t的最后一个字符加到u的末尾
• 求字典序最小的字符串u (长度必须为n，即s, t最后为空串)
• 1 ≤ n ≤ 1e5

算法分析：将t看做是栈stack，将u看做是队列queue，s作为向量vector

　　　　优先考虑将最小的比如说a,按照a的位置，将这个字符串分成几部分，如：dx|a|cdb|a|bsd

s: bsd

　　　 t:dxcdb

　　 u:aa

做成上述之后分别比较s和t中弹出的大小，先将小的放到前边，大的放到后边，最后得到最小字典序的字串；

代码如下：（在cf上有错误，卡在了第11条，也不知道怎么回事，只有一个字符不相等）

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

stack <int> sta;
vector <int> vec(26,0);
vector <int> vv;
queue <char> qu;

int main()
{
    string str;

    cin >> str;

    for(int i = 0; i < (int)str.length() ; i++)
    {
        vv.push_back(str[i] - 'a');
    }

    for(int i = 0 ; i < (int)str.length() ; i++)
    {
        vec[str[i]-'a']++;
    }

    int j;
    for(j = 0 ; j < (int)vec.size() ; j++)
        if(vec[j])
            break;

    int cnt = vec[j];

    while(1)
    {
        if(vv.front() != j)
        {
            sta.push(vv.front());
            vv.erase(vv.begin());
        }
        else
        {
            qu.push(vv.front() + 'a');
            vv.erase(vv.begin());
            cnt--;
        }
        if(cnt == 0)
            break;
    }

    while(!sta.empty() && !vv.empty())
    {
        if(vv.front() <= sta.top())
        {
            qu.push(vv.front() + 'a');
            vv.erase(vv.begin());
        }
        else
        {
            qu.push(sta.top() + 'a');
            sta.pop();
        }
    }
    if(!vv.empty())
    {
        while(!vv.empty())
        {
            sta.push(vv.front());
            vv.erase(vv.begin());
        }
    }
    if(!sta.empty())
    {
        while(!sta.empty())
        {
            qu.push(sta.top() + 'a');
            sta.pop();
        }
    }
    while(!qu.empty())
    {
        cout << qu.front() ;
        qu.pop();
    }

    return 0;
}

现在回过头来看这个题，明白了其实一开始理解就是错误的，不仅仅在一开始要这样进行，在之后比如说：

b a c d a c s b s a b d c s b c c

这一串，不仅仅对所有的a都是这样处理，

先处理成：

S: b d c s b c c

T:b c d c s b s

U:a a a

以上是之前理解的，在之后的操作出现问题，不应该将S和T进行大小比较，而应该对S串做进一步处理:对S中较小值b处理

S:c c

T:b c d c s b s d c s

U: a a a b b

继续对S处理

T:b c d c s b s d c s

U: a a a b b c c

将T全部出栈

U: a a a b b c c b c d c s b s d c s

以上才是正确的方法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

const int maxn = 100005;

int cnt[27];
stack <char> q;
char s[maxn];
string str;

bool Find_min(char c)
{
    int n = c - 'a';
    for(int i = 0 ; i < n ; i++)
    {
        if(cnt[i])
            return true;
    }
    return false;
}
void init()
{
    memset(cnt,0,sizeof(cnt));
    int len = str.size();
    for(int i = 0 ; i < len ; i++)
    {
        cnt[str[i]-'a']++;
    }
}

int main()
{
    while(cin >> str)
    {
        init();
        int l = str.size();

        q.push(str[0]);
        cnt[str[0]-'a']--;

        for(int i = 1 ; i < l ; i++)
        {
            while(!q.empty() && !Find_min(q.top()))
            {
                char tmp = q.top();
                cout << tmp;
                q.pop();
            }
            q.push(str[i]);
            cnt[str[i]-'a']--;
        }
        while(!q.empty())
        {
              cout << q.top();
              q.pop();
        }
    }
    
}

AC代码如下：