codeforces-1060B Maximum Sum of Digits-題解

題目：

任意給一個數 n ，把他分解為 n = a + b ，求 a 與 b 中的每一位數相加之和的最大值。

思路：

一：找出S的位數ant,A加上ant-1位9；eg：30000開始是9999

二：A的第一位為S第一位數字-1

此時A就變成了29999

三：算出B=S-A，拆位，輸出ans

（此時ans=1）

#include<cstdio>
#include<iostream>
using namespace std;
long long a=0,b,c,s,pow[20];
int ask(long long a)
{
    int cnt=0;
    while(a)
    {
        cnt=cnt+a%10;
        a/=10;
        }
    cnt=cnt+a;
    return cnt;
}
int main()
{
	pow[0]=1;
	for(int i=1;i<20;i++)
		pow[i]=10*pow[i-1];
	cin>>s;//s=30000
	c=s;//c=30000
	int ant=0;
	while(s/10){
        a=a*10+9;//9,99,999,9999，算出最高位後的數字 eg：9999 
        s/=10;//3000,300,30,3
        ant++;//1,2,3,4
    }
	a=a+(s-1)*pow[ant];//算出最高位上的數字 eg：2 
    b=c-a;
	cout<<ask(a)+ask(b)<<endl;
	return 0; 
} 
           

S(a)+S(b)是如何變大的？考慮b任意一個數位，當其從0變為9，S(a)增大1，S(B)增大8；當是其它情況時（數位變化不跨越0），相當于S(a)+x, S(b)-x，S(a)+S(b)不變。總結起來，劃分（a，b）時讓盡量多的數位變化能夠跨越0，等于讓b的每一位盡量分最多出來。得到貪心政策，每一數位都分9出來。