P8482 Number指针做法

Dove_Pig · 2022-08-26 13:21:59 · 题解

前言：当蒟蒻猪猪在月赛中第三题爆零，看着机房里各位一个接一个通过第三题，改了不知多少次后，颤颤巍巍地提交最后的代码，终于！

因为过了前三题，猪猪成功挤进月赛排名第三页，并在八月二十二日成功橙名，芜湖！

那么进入正题，一看到第三题，猪猪第一想法就是辗转相互给数字，假定两个数字 a 和 b ，我们将数字两个两个处理把最大的先给 a ，然后再给 b ，之后反过来把大的先给 b ，小的给 a ，这样可以保证大的数字都在尽可能高位，相互乘积最大，最后如果还有剩一个数字就给小的那个。然后呢，成功全红爆零。为什么会出问题？将数字大的放在尽可能高位是没有问题的，但是辗转相互给数字就会出问题。举个例子，假如 0 到 9 各一个，我们按辗转相互给，会得到 96521 和 87430 ， 乘积为 8438831030 ，但非常明显的，将其分成 96420 和 87531 乘积 8439739020 会更大。所以说明刚才的策略有问题，那么该怎么办呢？就在机房众人鸦雀无声，气氛沉死如万军战前摆阵之际，帅气的 NBest 站了出来提出指针法，猪猪恍然大悟，犹如拨云见日茅塞顿开般怒砍第三题五十分。

那么我们想想，按照越大的数字位数越高的策略， a+b 一定是固定的，那么根据小学三年级数学来解释， |a-b| 差值越小，乘积将越大。那么我们就可以用两个指针存入数字，再给两个指针判断两个数的大小，从高位开始，如果数字一样就指向下一个，不一样就可以得出 a 与 b 之间的大小关系，之后就直线存入数字就可以了。

第一个问题已经迎刃而解，我们拿到了五十分，那么第二个问题，怎么转换成两个不同的数字之和？请大家仔细看数据给定，保证 1 \le c_i 这说明什么？这说明肯定有个零！有零不就好了，把 0 踢掉一个，换成 2 和 5 分别给 a 和 b 两个数用高精乘乘上，然后，就收工了？没错，就这么简单。

最后献上丑陋的代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+5;
long long num;
int a[MAXN],b[MAXN],c[10];
int main(){
    for(int i=0;i<=9;i++){
        scanf("%d",&c[i]);
        num+=c[i];
    }
    int aes=0,bes=0,ces=9,zz=0;//aes表示a指针，bes表示b指针，ces指向数字，zz是公用大小指针
    bool ok=0;
    while(num){
        num-=2;
        if(a[zz]==b[zz]){//一样就随便存
            zz++;
            if(!c[ces])ces--;
            aes++;
            a[aes]=ces;
            c[ces]--;
            if(!c[ces])ces--;
            bes++;
            b[bes]=ces;
            c[ces]--;
        }
        else if(a[zz]<b[zz]){//不一样就给小数大的数字存
            if(!c[ces])ces--;
            aes++;
            a[aes]=ces;
            c[ces]--;
            if(!c[ces])ces--;
            bes++;
            b[bes]=ces;
            c[ces]--;
        }
        else if(a[zz]>b[zz]){//反之
            if(!c[ces])ces--;
            bes++;
            b[bes]=ces;
            c[ces]--;
            if(!c[ces])ces--;
            aes++;
            a[aes]=ces;
            c[ces]--;
        }
        if(num==1){//如果最后只剩一个数给小的数存，保证两个数字差值最小
            while(!c[ces])ces--;
            if(a[zz]<b[zz]){
                aes++;
                a[aes]=0;
            }
            else{
                bes++;
                b[bes]=0;
            }
            break;
        }
    }
    if(a[aes]==0){//判断0在哪里，进行高精操作
        aes--;
        for(int i=aes;i>=1;i--){
            a[i]*=2;
        }
        for(int i=aes;i>=1;i--){
            if(a[i]>=10){
                a[i-1]+=a[i]/10;
                a[i]%=10;
            }
        }
        for(int i=bes;i>=1;i--){
            b[i]*=5;
        }
        for(int i=bes;i>=1;i--){
            if(b[i]>=10){
                b[i-1]+=b[i]/10;
                b[i]%=10;
            }
        }
    }
    else{
        bes--;
        for(int i=aes;i>=1;i--){
            a[i]*=2;
        }
        for(int i=aes;i>=1;i--){
            if(a[i]>=10){
                a[i-1]+=a[i]/10;
                a[i]%=10;
            }
        }
        for(int i=bes;i>=1;i--){
            b[i]*=5;
        }
        for(int i=bes;i>=1;i--){
            if(b[i]>=10){
                b[i-1]+=b[i]/10;
                b[i]%=10;
            }
        }
    }
    if(a[0])cout<<a[0];//考虑a进位问题
    for(int i=1;i<=aes;i++){
        printf("%d",a[i]);
    } 
    printf("\n");
    if(b[0])cout<<b[0];//考虑b进位问题
    for(int i=1;i<=bes;i++){
        printf("%d",b[i]);
    }
    return 0;
}

祝大家绿题经验加加！