POI2019 Pomniejszenie

题目大意：给两个数$A，B$。要求在$A$里面恰好选$k$位，改变它们的值，让$A$小于$B$ 且$A$最大。

先复习一下，两个$n$位的数$A,B$，如何比较它们的大小？

很简单，如果$A,B$的前$i-1$位都一模一样，但是$A$的第$i$位大于$B$的第$i$位那么后边不用看了，$A$必然大于$B$ 。

好了回来继续看这个题，那么我们要让$A$小于$B$，就要选择一个目标位$Tar$，使得$A$的前$Tar$位都和$B$的前$Tar$位相同，而$A$的$Tar$位恰好等于$B$的$Tar$位$-1$。

现在$A$小于$B$在思想上已经搞定了，我们需要考虑还要让$A$最大的事情了，这个事情也很简单，剩下所有位都是$9$的话不就可以了么。

以上两段就是本题最关键的贪心思想，现在我们来开始做这个题。

首先是找这个$Tar$。 $Tar$怎么找？可以一位一位枚举，看看这一位可以不可做这个$Tar$，而且为了让$A$尽可能大，这个$Tar$我们要让它尽量靠后。（例子：$A:234$ ; $B:547$ 例子里我们先不考虑k啊; 因为第$Tar$位是决定$A$和$B$大小的一位，如果$Tar=1$，那么按照我们的贪心，$A=499$, 而$Tar=2$时，$A=539$, 当$Tar=3$时，$A=546$，很容易看出来$Tar$越大，得到的$A$越大）

但是因为有k的限制，我们的$Tar$也不能太大了，至少说当我们想要取第$i$位做$Tar$时，得保证前$i$位$A,B$不同的位数+$i$后面还剩下的位数得大于等于$k$。

现在我们有疑问了，首先是我前面一直在说“前$i$位$A,B$的不同的位数”，但是我们还没算第$Tar$位呢，第$Tar$位如果说$A$大于$B$，那么我们的操作是让$A_{Tar}=B_{Tar}-1$吧？其实不一定，如果$B_{Tar}=0$怎么办？其次是我前面说 “剩下所有位都是$9$的话不就可以了么。” ，很显然啊，如果原来$A$的后面几位中就有 $’9’$怎么办啊。

现在我们一个个解决疑问，首先如果$B_{i}=0$ 那么这一位不可能成为$Tar$，我们在枚举的时候要跳过去，(要是还需要问这个的原因的话：因为如果$A,B$前$Tar$位相同，而$B_{Tar}=0$那么不管$A_{Tar}$等于几，都不能让$A < B$，和我们最开始给$Tar$的定义就矛盾了)

其次如果$A$的后几位中本来就有$’9’$那么当我们把$A$的$Tar$位后面的不是$9$的位都变成$9$之后，如果这个时候变换次数仍然不够$k$次，我们应该从后往前把$A$中原来就是$9$的位变成$8$（如果还需要问为什么这样最优：因为在前$Tar$位都确定了，并且$Tar$后面的位都是$9$的前提下，假如，我们还需要变$x$个数，然后呢，$A$数组的$Tar$位之后有$y$个本来就是$9$的位, $x\le y$ ,那么，为了把这$x$个操作做完，我们必须得拿这些原来就是$9$的位开刀了，而且一过脑子就能想出来，肯定是从后往前把那些本来就是$9$的位变成$8$）

我感觉我写的非常啰嗦，主要是为了能让更多的人看明白。（~~其实是我语文太差了~~）

上面一堆废话只为了介绍思想，现在我们把所有东西串起来，说一下写法。

首先读入数据，用$len$表示数的长度，然后从$1$到$len$枚举每一位，当枚举到第$i$位时，如果$B_{i}=0$直接跳过，否则来判断这个$i$能不能当$Tar$，最后枚举完了，我们也找到了最优的$Tar$。现在我们要开始构造答案了，第一步是$Tar$以前的每一位$A_{i}=B_{i}$，第二步是决定第$Tar$位怎么变，如果$A_{Tar}\ge B_{Tar}$ 或者$A_{Tar}< B_{Tar}-1$，那么$A_{Tar}= B_{Tar}-1$ ；如果$A_{Tar}=B_{Tar}-1$ 那就先不动它了。第三步是把$Tar$以后的不等于$9$的位都变成$9$，第四步是把原来就是$9$的从后往前变成$8$，第五步是，如果在第三步中 “那就先不动它了” 这样的情况发生的话，有可能这个时候我们的变换次数离$k$还差$1$，这个时候我们最优的操作就是 “动它” 把$A_{Tar}$减去$1$;（注意：以上五步，第一步是必走的，在$A_{Tar}\ge B_{Tar}$的情况下，第二步必走，其他几步，都是要看我们当前的操作数，有没有到$k$，不到的话，再操作。）

到这里可能还有一个疑问，就是为啥这样子，到最后能保证恰好换$k$次？因为如果换不到$k$次，我们会第二步，第三步，一直进行下去。那为啥不会出现第五步走完还不够$k$次？前面写了$->$“我们的$Tar$也不能太大了，至少说当我们想要取第$i$位做$Tar$时，得保证前$i$位$A,B$不同的位数+$i$后面还剩下的位数得大于等于$k$。”不过这句话不够严谨，应该分三部分，前$i-1$位中不同的位数（$cnt1$），$i$位之后剩余的位数($cnt2$)，第i位（$1$）, $cnt1+cnt2+1\ge k$ 这样子，如果$cnt1+cnt2+1>k$ 即$cnt1+cnt2\ge k$ 那么就算第二步得到时候我们 “那就先不动它了” 也最多进行到第四步结束。如果$cnt1+cnt2+1=k$ 那么如果第二步我们 “那就先不动它了” 就会出现，当把第四步做完时，$cnt1,cnt2$都做了，还差$1$，就要做第五步了。

参考代码：仅供参考，因为菜菜的我改了好几遍才过，所以代码中赘余的成分比较多，比如一个if就行的整了好几个if，一个变量就够的用了好几个变量23333.

而且大概是我自带大常数，O(n)的算法，我写出来就是900ms险过，我同学就是400ms稳过，qwq哭了///

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=100010;
int t,k;
char A[Maxn],B[Maxn];
int a[Maxn],b[Maxn]; //用a,b分别存A,B
void Solve()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s%d",A+1,B+1,&k);
        int len=strlen(A+1);
        for(int i=1;i<=len;i++) a[i]=A[i]-'0',b[i]=B[i]-'0';
        int cnt=0,Tar=-1;
        //cnt是用来记录前i位不同的位数，而nowc呢，我这里写的比较冗长，其实并没啥用。
        for(int i=1;i<=len;i++)
        {
            if(b[i])
            {
                int nowc=0;
                if(a[i]>=b[i])
                {
                    nowc=cnt+1;
                    if(nowc<=k&&nowc+len-i>=k) Tar=i;
                }
                else 
                {
                    if(b[i]>1)
                    {
                        nowc=cnt;
                        if(nowc<=k&&nowc+len-i+1>=k) Tar=i;
                    }
                    else
                    {
                        nowc=cnt;
                        if(nowc<=k&&nowc+len-i>=k) Tar=i;
                    }
                    
                }
            }
            if(a[i]!=b[i]) cnt++;
        }

        if(Tar==-1){printf("-1\n"); continue ;}
        
        cnt=0;
        for(int i=1;i<=Tar-1;i++) if(a[i]!=b[i]) cnt++,a[i]=b[i];
        
        if(a[Tar]>=b[Tar]) cnt++,a[Tar]=b[Tar]-1;
        else if(cnt<k&&a[Tar]!=b[Tar]-1) cnt++,a[Tar]=b[Tar]-1;
        
        if(cnt<k)
        {
            for(int i=Tar+1;i<=len;i++) if(A[i]!='9'&&cnt<k) cnt++,a[i]=9;
        }
        if(cnt<k)
        {
            for(int i=len;i>=Tar+1;i--) if(A[i]=='9'&&cnt<k) cnt++,a[i]=8;
        }
        
        if(cnt==k-1) cnt++,a[Tar]--;
        for(int i=1;i<=len;i++) printf("%d",a[i]); puts("");
    }
}
int main()
{
    Solve();
    return 0;
}