最大和题解

S__X · 2023-01-24 16:19:51 · 题解

题目简化

给你一个数，从它的个位到最高位进行操作，对于其每一位，你可以选择让他增加 1，减少 1（如果当前位是 0，减 1 后会退位） 或者不变。

分析

要使每一位的总和最大，我们可以对每一位进行判断。

• 如果当前位不是 0 和 9，那么显然要加一。如：12，最大总和即为每一位加一再相加。

• 如果当前位是 0 就减一。简单证明： -1 后，当前位变成 9，下一位因为退位需要 -1。这样子总和增加了 9-1=8，显然比增加 1 更优。如 100，最大总和即为个位减一再相加 (99)。当然，如果 a=0 就要特判。

• 当前位上的数值为 9 时，不需要操作，证明平凡，和上面相似。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,sum=0;
        cin>>a;
        if(a==0) sum=1;//特判
        else {
            while(a!=0){
                if(a%10==0) a-=1;//当前值为0时
                else if(a%10!=9) a+=1;//当前值为1~8时
                //为9时不变
                sum+=(a%10);//加和
                a/=10;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}