题目链接

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
ans:
possible
606
900
906
907

3
606
600
606
ans:
possible
606
900
906

3
666
606
606
ans:
possible
666
906
906

3
666
609
606
ans:
possible
666
906
906

3
660
606
600
ans:impossible
*/

后记

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