已有的题解或是说的太麻烦了,或是一笔带过,本篇题解决定简明扼要地好好讲一讲。
题意
题目链接 大体题意不再阐述,注意你只能根据给出的规则更换一段数而不能隔开来换就好了。
解析
已有的题解也都提到了,遇到第一个 $b_{num_i}>num_i$ ( $b$ 数组为更换规则,$num$ 数组为每一位的数字)时开始更换,一直更换到 $b_{num_i}<num_i$ 为止。
那么,为什么呢?
首先我们知道,越是高位增大,效益就越大, 因此我们要尽早开始更换,也就是从第一个可以变大的最高位开始,而又由于题目中要求更换的是一段数,同样的,越是高位变小,亏损就越大,因此我们要在找到第一个会变小的数时就及时止损,即停止更换并退出。
至于为什么是 $>$ 而不是 $\ge$ 呢?
显然的,我们找到第一个 $b_{num_i}\ge num_i$ 的数时,我们如果直接进行更换,那就容易过早碰壁,且这个行为时毫无意义的,这样还不如放到后面换。
例:样例一中的数若改为 $1733$ 则采用 $\ge$ 在替换了第一个数后,碰到 $7$ 就会停止,而实际上应该把这次更换的机会留下来,从第三位开始更换。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,num[N],b[N];
char a[N];
bool flag;
int main(){
scanf("%d",&n);
scanf("%s",a+1);
for(int i=1;i<=n;i++)
num[i]=a[i]-'0';
for(int i=1;i<=9;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
if(b[num[i]]>num[i]){
if(!flag) flag=true;//flag 判断有无开始更换
num[i]=b[num[i]];
}
else if(b[num[i]]<num[i])
if(flag) break; //若开始更换后碰到会亏损的数,就退出
}
for(int i=1;i<=n;i++)
printf("%d",num[i]);
return 0;
}
琐记
这题恶意评分了吧,实际难度橙或黄差不多了吧。