【基础算法练习题】CF490E加强

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
string s[MAXN + 5];
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    // s[1] 置最小
    if (s[1][0] == '?')
        s[1][0] = '1';
    for (int j = 0; j < s[1].size(); j++)
        if (s[1][j] == '?')
            s[1][j] = '0';
    // 依次处理，把 s[i] 变成大于 s[i-1] 数中最小的
    for (int i = 2; i <= n; i++)
    {
        if (s[i].length() < s[i - 1].length())
        {
            cout << "NO\n";
            return 0;
        }
        if (s[i].length() > s[i - 1].length())
        {
            if (s[i][0] == '?')
                s[i][0] = '1';
            for (int j = 0; j < s[i].size(); j++)
                if (s[i][j] == '?')
                    s[i][j] = '0';
            continue;
        }
        bool limit = true; // 前面是否相等
        int last = -1;     // 上一个可以调整的 ? 的位置
        string temp = s[i];
        for (int dig = 0; dig < s[i].length(); dig++)
        {
            if (s[i][dig] != '?')
            {
                if (s[i][dig] > s[i - 1][dig])
                    limit = false;
                if (limit && s[i][dig] < s[i - 1][dig])
                {
                    if (last == -1)
                    {
                        cout << "NO\n";
                        return 0;
                    }
                    else
                    {
                        s[i][last] = s[i - 1][last] + 1;
                        for (int k = last + 1; k < dig; k++)
                            if (temp[k] == '?')
                                s[i][k] = '0';
                        limit = false;
                    }
                }
            }
            else if (s[i][dig] == '?')
            {
                if (!limit)
                {
                    if (dig == 0)
                        s[i][dig] = '1';
                    else
                        s[i][dig] = '0';
                }
                else
                {
                    if (s[i - 1][dig] == '9')
                        s[i][dig] = '9';
                    else
                    {
                        s[i][dig] = s[i - 1][dig];
                        last = dig;
                    }
                }
            }
        }
        cout<<endl;
        if (limit && last == -1)
        {
            cout << "NO\n";
            return 0;
        }
        if (limit)
        {
            s[i][last] = s[i - 1][last] + 1;
            for (int k = last + 1; k < s[i].length(); k++)
                if (temp[k] == '?')
                    s[i][k] = '0';
        }
    }
    cout << "YES\n";
    for (int i = 1; i <= n; i++)
        cout << s[i] << "\n";
    return 0;
}