欢乐赛#33 题解 T6

A33700.字典序问题

1. 整体思路

   • 我们要想办法构造出一个可能的字典序最大的字符串。考虑到数字越大在字典序中越靠后，所以要尽量让高位数字尽可能大。
   • 因为 n 的取值范围可能很大（从代码中看，是用字符串来接收 n 的，这也暗示了 n 可能是非常大的数），所以我们通过对 n 的字符串表示进行分析和操作来找到答案。

2. 具体步骤

   • 首先，判断 n 是否全部由数字 9 组成。如果是，那字典序最大的字符串就是 n 本身啦，不过代码里没有显式地处理这种全 9 的情况，我们先接着往下看一般情况的处理。
   • 然后，我们先构造一个临时字符串 tmp，它的长度是 n 的长度减1，并且每个字符都是 9。为什么要这样做呢？因为我们要让高位尽可能大，所以先假设高位都是 9，然后再根据实际情况进行调整。假设现在有一个5位数，那么9999算是最大的数字，除非这个5位数是9999?,所以需要对最后一位数字进行判断。
   • 最后，我们再看 n 的最后一位数字。如果 n 的最后一位不是 0，并且 n 的前 len - 1 位（也就是去掉最后一位的部分）组成的字符串大于等于我们刚才构造的 tmp，那就把 n 的最后一位数字加到 tmp 后面。这样得到的 tmp 就是我们要找的字典序最大的字符串啦。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

string n, tmp;
int len;

int main()
{
    cin >> n;
    len = n.size();
    for (int i = 0; i < len - 1; i++)
        tmp += '9';
    if (n[len - 1] != '0' && n.substr(0, len - 1) >= tmp)
        tmp += n[len - 1];
    cout << tmp;
    return 0;
}