https://ac.nowcoder.com/acm/contest/318/G
题解:本题考验的是简单的贪心思维。通过题目我们可以了解到要使得 f (x)尽可能的大,就是要使得x 中的9尽可能的多。所以对于本题,我们可以考虑构造出一个最大的a,使得这个a满足它的每一位都是9且a<=c,接着我们再令b = c - a,将a 和 b 分别代入 f (x)中,求得最后的答案即可。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=10000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,q;
int f(ll x){
int tmp = 0;
while(x != 0){
tmp += x % 10;
x /= 10;
}
return tmp;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~scanf("%lld",&n)){
ll i=9;
for(;i<=n;i=i*10+9);
cout << f(i/10)+f(n-i/10) << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ll n, a, b;
while(cin >> n) {
ll m = n, k = 9;
while(m >= k) {
k = k * 10 + 9;
}
k /= 10;
a = k;
b = n - k;
ll sum = 0;
while(a) {
sum += a % 10;
a /= 10;
}
while(b) {
sum += b % 10;
b /= 10;
}
cout << sum << endl;
}
return 0;
}