算法知识点: 二分图,栈,染色法,贪心

复杂度：

解题思路：

如果只有一个栈，则整个操作顺序是固定的：

  • 从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。

因此，我们只需考虑将每个数分配给哪个栈即可。

这里有个很强的性质：

两个数 不能被放入同一个栈中，当且仅当存在 且 。

有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。这一步可以转化成图论问题：

  • 如果i, j满足条件，则在i和j之间连一条边。

然后判断是否是二分图即可。

答案要求字典序最小，因此从前往后染色时，需要优先将当前点分配到第一个栈中。

C++ 代码： 

#include <iostream>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std; const int N = 1010;
 
int n;
int a[N], f[N];
int color[N];
bool g[N][N];
 
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = 1; i <= n; i++)
        if (g[u][i])
        {
            if (color[i] == c) return false;
            if (color[i] == -1 && !dfs(i, !c)) return false;
        }
 
    return true;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        f[n + 1] = n + 1;
        memset(g, false, sizeof g);
        for (int i = n; i; i--) f[i] = min(f[i + 1], a[i]);
 
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (a[i] < a[j] && f[j + 1] < a[i])
                    g[i][j] = g[j][i] = true;
 
        memset(color, -1, sizeof color);
 
        bool flag = true;
        for (int i = 1; i <= n; i++)
            if (color[i] == -1 && !dfs(i, 0))
            {
                flag = false;
                break;
            }
 
        if (!flag)
        {
            cout << 0 << endl;
            continue;
        }
 
        stack<int> stk1, stk2;
 
        int now = 1;
        for (int i = 1; i <= n; i++)
        {
            if (color[i] == 0)
            {
                stk1.push(a[i]);
                cout << "a ";
            }
            else
            {
                stk2.push(a[i]);
                cout << "c ";
            }
 
            while (true)
                if (stk1.size() && stk1.top() == now)
                {
                    stk1.pop();
                    cout << "b ";
                    now++;
                }
            else if (stk2.size() && stk2.top() == now)
            {
                stk2.pop();
                cout << "d ";
                now++;
            }
            else break;
        }
        cout << endl;
    }
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ