【题解】POJ3617

题目：http://poj.org/problem?id=3617

使用贪心算法，从s字符串的首尾选择字典序较小的，加到t的末尾。当s首尾字母相同时，就往中间一位进行比较，最终哪边的小，就把那边的字母加到t的末尾。这样主要是为了让较小的字母更快出现

然后要注意的是题目中要求了，一行最多输出80个字母。这点要注意，我就被坑了。

代码：

#include <iostream>
#include <vector>
using namespace std;
#define MAXN 2005
int n;

char s[MAXN];
char t[MAXN];

void solve()
{
    int sl = 0, sr = n - 1;
    int tl = 0;

    

    while (tl != n)
    {
        
        if (s[sl] != s[sr])
        {
            if (s[sl] < s[sr])
            {
                t[tl] = s[sl];
                ++sl;
                ++tl;
            }
            else
            {
                t[tl] = s[sr];
                --sr;
                ++tl;
            }

        }
        else
        {
            bool choose_left = false;
            int l=sl,r=sr;
            while(s[l]==s[r]&&l<r)
            {
                l++,r--;
                if(s[l]<s[r])
                {
                    choose_left = true;
                    break;
                }
                else if(s[l]>s[r])
                    break;
            }

            if(choose_left)
            {
                t[tl] = s[sl];
                sl++;
                tl++;
            }
            else
            {
                t[tl] = s[sr];
                sr--;
                tl++;
            }
        }
    }

    int cnt=0;
    for(int i=0;i<tl;++i)
    {
        cout<<t[i];
        ++cnt;
        if(cnt%80==0)
            cout<<endl;

    }
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> s[i];
    
    solve();
}

转载请注明原文：https://www.longjin666.top/?p=1094

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~