2021年度训练联盟热身训练赛第五场 H题 In-place Sorting

题目链接

https://ac.nowcoder.com/acm/contest/13926/H

题意

给你n个数字，你可以将每个数字中存在的6改成9，也可以9改成6，当然也可以选择不更改。
你需要使得最后n个数字的排列是非递减的，若无法构造则输出impossible。

思路

贪心构造，使每个串在大于等于前一个串的前提下尽可能小。注意字符串之间的大小比较与数字之间大小比较的不同（以字符串形式输入数字）。

依次遍历n个串，分情况构造：

1. 当前串长度 > 前一个串长度。那直接把当前串的所有9变成6就可以了，变完之后当前串肯定还是大于前一个串。
2. 当前串长度 < 前一个串长度。就算把当前串的所有6变成9也无力回天了，直接impossible结束。
3. 当前串长度 = 前一个串长度。先还是把当前串的所有6变成9，如果还是比前一个串小，直接impossible结束；否则，从高位到低位，依次尝试把9变回6，这个时候要注意，如果变了之后比前一个串小了，那就说明不能变，一定要还原回去！

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
string s[N];
bool judge()
{
    for(int i=1;i<=n;i++)
    {
        if(i==1||s[i].length()>s[i-1].length()) // 肯定比前面的要大，直接全部变小；特判i=1
        {
            for(int j=0;s[i][j];j++)
                if(s[i][j]=='9')s[i][j]='6';
        }
        else
        {
            if(s[i].length()<s[i-1].length())return 0;
            // 接下来是长度相等的情况
            for(int j=0;s[i][j];j++) // 先尽量都变成最大的9
                if(s[i][j]=='6')s[i][j]='9';
            if(s[i]<s[i-1])return 0; // 全变最大都满足不了
            for(int j=0;s[i][j];j++) // 从高位到低位尝试变小
            {
                if(s[i][j]=='9')
                {
                    s[i][j]='6';
                    if(s[i]<s[i-1]) // 不能变，还原
                        s[i][j]='9';
                }
            }
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    if(judge())
    {
        printf("possible\n");
        for(int i=1;i<=n;i++)
            printf("%s\n",s[i].c_str());
    }
    else printf("impossible\n");
    return 0;
}
/*
4
606
900
606
907

possible
606
900
906
907
*/

后记

比赛的时候想了一堆奇怪的思路，先想着贪心，考虑了一堆细节，然而思路就是错的；
后来就暴力莽，想着对于所有6和9的出现位置可以选6或者选9，那么有2^18^种排列，数据量2^18^*10^4^，妥妥的超时...