题目链接
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^,妥妥的超时...
Comments | NOTHING