ACM模版

描述

题解

这道题很有趣，为了达到最小字典序，那么x一定是固定的，一定是第一个提前出现的字母的位置，比如abfde，f位置按字典序应该是d，f属于提前出现的，所以x定位在2，接着，我们往后边查找d，把所有查找到的合法位置存入y[]中，如果只有一个，那么就是y[0]，否则需要从所有的可能结果中寻找按字典序最小并且y最小的结果……

说到这里，也就是问题的关键出来了，怎么才算是符合要求的y呢？
当然，我们需要将两两结果进行对比，先对ansY到x与y[j]到y[j] - ansY + x进行对比，如果后者小于前者，则更新答案，相等则continue，大于则直接跳出，然而这里存在一个特殊情况，如果一直continue呢？比如说xazxa，两截儿完全相同的情况，这时我们就要从位置3向前推，位置1向后推，逐个对比（不包括3和1），一直到x的位置即可。这样，我们通过同样的取舍标准即可得到争取答案。

AC……

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 2505;
const int MAXL = 26;

int letter[MAXL];
char s[MAXN];

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int T;
    cin >> T;

    while (T--)
    {
        int x = 0;
        int y[MAXN] = {
  0};
        memset(letter, 0, sizeof(letter));
        cin >> s;
        int len = (int)strlen(s);
        int i;
        for (i = 0; i < len; i++)
        {
            letter[s[i] - 'a']++;
        }
        for (i = 0; i < MAXL; i++)
        {
            if (!letter[i])
            {
                continue;
            }
            for (int j = 0; j < len; j++)
            {
                while (!letter[i])
                {
                    i++;
                }
                if (s[j] - 'a' == i)
                {
                    letter[i]--;
                }
                else
                {
                    x = j;
                    int key = 0;
                    for (int k = j + 1; k < len; k++)
                    {
                        if (s[k] - 'a' == i)
                        {
                            y[key++] = k;
                            if (key == letter[i])
                            {
                                break;
                            }
                        }
                    }
                    break;
                }
            }
            break;
        }
        int ansY = y[0];
        for (int j = 1; j < letter[i]; j++)
        {
            bool flag = true;
            for (int k = 1; k < ansY - x + 1; k++)
            {
                if (s[ansY - k] > s[y[j] - k])
                {
                    ansY = y[j];
                    flag = false;
                    break;
                }
                else if (s[ansY - k] < s[y[j] - k])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                for (int k = 1; k < y[j] - ansY + 1; k++)
                {
                    if (s[ansY + k] > s[y[j] - ansY + x - k])
                    {
                        ansY = y[j];
                        break;
                    }
                    else if (s[ansY + k] < s[y[j] - ansY + x - k])
                    {
                        break;
                    }
                }
            }
        }

        cout << x << ' ' << ansY << '\n';
    }

    return 0;
}