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處理

S:

U: a a a b b c c

将T全部出棧

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代碼如下：

代碼改變世界