E. Sum of Digits
题意
给定 n 和 k (1≤n≤150,0≤k≤9) ，找到最小的 x ，使得：
f(x)+f(x+1)+⋯+f(x+k)=n
其中f(x) 表示 x 的十进制数字的和
若不存在x则输出-1
题解
贪心的想:用最少位的数来构造出n
那么尽量用更多的9来减少x的位数才能使得答案最小
注意到n最大150 , 150/9 <= 17 那么所有小于150的n能用f(x)+f(x+1)+⋯+f(x+k)来表示的x一定不超过longlong
而使用9来构造x导致了进位问题 不过题面条件限制k<=9
意味着 x,x+1,x+2,….,x+k最多只进位一次
于是把数x拆分成4个部分来暴力枚举
首先考虑个位数。 因为k<=9所以最直接影响到的是个位数上的数字
其次是个位之前有多少个连续的9。 因为个位数的进位会直接影响到十位以及之前的连续的9
枚举x这两部分的值后可以直接计算k+1个数对答案产生的贡献 sum
具体的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| for(int lastnum=0;lastnum<=9;lastnum++){
for(int suf9=16;suf9>=0;suf9--){
ll sum=0,cnt=1;ll temp=lastnum;
while(cnt<=suf9){
temp+=9*qpow(10,cnt);
cnt++;
}
for(int i=0;i<=k;i++){
if(lastnum+i<10)sum+=(9*suf9+lastnum+i);
else sum+=(1+(lastnum+i)%10);
}
}
}
|
然后rest=n-sum
如果rest<=8那么当前枚举的符合要求的x首位就是8 后面接上枚举的连续的9和个位数值
否则 答案x需要在最前面插入一个8(因为suf9讨论的是个位进位会直接影响到的十进制位,8是最大的且不受后面进位影响的数) 然后贪心的填充余下 更高位的数
具体的
1
2
3
4
5
6
7
8
9
10
11
12
| if(n<sum)continue;
if((n-sum)%(k+1))continue;
ll rest=(n-sum)/(k+1);
if(rest>8)temp+=8*qpow(10,cnt),cnt++,rest-=8;
while(rest>8){
temp+=9*qpow(10,cnt);
cnt++;
rest-=9;
}
temp+=rest*qpow(10,cnt);
ans=min(ans,temp);
|
于是这样贪心构造出最后的x一定符合
首位 9999 8 9999 末位 这种形式
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int mod=2e3;
const int Max=2e6+5;
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans*=x;
x*=x;y>>=1;
}
return ans;
}
int main(){
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;ll ans=1e18;
for(int lastnum=0;lastnum<=9;lastnum++){
for(int suf9=16;suf9>=0;suf9--){
ll sum=0,cnt=1;ll temp=lastnum;
while(cnt<=suf9){
temp+=9*qpow(10,cnt);
cnt++;
}
for(int i=0;i<=k;i++){
if(lastnum+i<10)sum+=(9*suf9+lastnum+i);
else sum+=(1+(lastnum+i)%10);
}
if(n<sum)continue;
if((n-sum)%(k+1))continue;
ll rest=(n-sum)/(k+1);
if(rest>8)temp+=8*qpow(10,cnt),cnt++,rest-=8;
while(rest>8){
temp+=9*qpow(10,cnt);
cnt++;
rest-=9;
}
temp+=rest*qpow(10,cnt);
ans=min(ans,temp);
}
}
if(ans!=1e18)cout<<ans<<endl;
else cout<<-1<<endl;
}
}
|