贪心 ---- Educational Codeforces Round 90 (Rated for Div. 2)E. Sum of Digits[数位贡献+思维题+贪心]

题目链接

题目大意：就是给你nnn和kkk然后再定义一个函数f(x)是十进制数x各个位数之和f(x)是十进制数x各个位数之和f(x)是十进制数x各个位数之和

叫你求出最小的x使得f(x)+f(x+1)+...+f(x+k)=n∣k∈[0,9],n∈[1,150]叫你求出最小的x使得f(x)+f(x+1)+...+f(x+k)=n|k\in[0,9],n\in[1,150]叫你求出最小的x使得f(x)+f(x+1)+...+f(x+k)=n∣k∈[0,9],n∈[1,150]

解题思路：首先我们发现两个规律：

1.就是x+kx+kx+k我们最多进位一次

2.你要是想进位的话你要取决俩个东西

1):就是你个位数的大小

2):就是你个位数之后9的个数

3.当上面两个确定之后高位就贪心选

4.还有一个细节就是这(k+1)(k+1)(k+1)个数的高位应该是一样的

5.那么我们就可以枚举个位数以及个位之后会9的个数

主函数

int T;read(T);while(T --){cin >> n >> k;ll ans = 1e18;_for(i,0,17)//枚举9的个数_for(j,0,10)//枚举个位ans = min(ans,num(n,k,i,j));if(ans == 1e18) ans = -1;cout << ans << endl;}

首先我们先讲已经确定的各位数字之和先加上

ll num(int n, int k, int c9, int r) //函数头{int res = 0;_for(i,0,k+1) {if (i + r < 10) {res += i + r + 9 * c9;} else {res += i + r - 9;}}

判断一下还剩下数的多少，因为后面的k+1个数的高位都是一样的

int need = n - res;if (need % (k + 1) || need < 0){return 1e18;}

贪心选取每一位

need /= k + 1;ll ans = 0;if (need < 9){ans = need;}else {need -= 8;int t = need % 9;ans = t;for (int i = 1; i <= need / 9; i++) {ans = ans * 10 + 9;}ans = ans * 10 + 8;}// 这里就是将高位和低位拼接起来for (int i = 1; i <= c9; i++) {ans = ans * 10 + 9;}ans = ans * 10 + r;return ans;}

完整代码

#include <iostream>#include <cstdio>#include <stack>#include <sstream>#include <vector>#include <map>#include <cstring>#include <deque>#include <cmath>#include <iomanip>#include <queue>#include <algorithm>#include <set>#define mid ((l + r) >> 1) #define Lson rt << 1, l , mid#define Rson rt << 1|1, mid + 1, r#define ms(a,al) memset(a,al,sizeof(a))#define log2(a) log(a)/log(2)#define _for(i,a,b) for( int i = (a); i < (b); ++i)#define _rep(i,a,b) for( int i = (a); i <= (b); ++i)#define for_(i,a,b) for( int i = (a); i >= (b); -- i)#define rep_(i,a,b) for( int i = (a); i > (b); -- i)#define lowbit(x) ((-x) & x)#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)#define INF 0x3f3f3f3f#define hash Hash#define next Next#define count Count#define pb push_back#define f first#define s secondusing namespace std;const int N = 1e6+10, mod = 1e9 + 7;const double eps = 1e-10;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> PII;template<typename T> void read(T &x){x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;}template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);}int n, k;ll num(int n, int k, int c9, int r) {int res = 0;_for(i,0,k+1) {if (i + r < 10) {res += i + r + 9 * c9;} else {res += i + r - 9;}}int need = n - res;if (need % (k + 1) || need < 0){return 1e18;}need /= k + 1;ll ans = 0;if (need < 9){ans = need;}else {need -= 8;int t = need % 9;ans = t;for (int i = 1; i <= need / 9; i++) {ans = ans * 10 + 9;}ans = ans * 10 + 8;}for (int i = 1; i <= c9; i++) {ans = ans * 10 + 9;}ans = ans * 10 + r;return ans;}int main(){int T;read(T);while(T --){cin >> n >> k;ll ans = 1e18;_for(i,0,17)_for(j,0,10)ans = min(ans,num(n,k,i,j));if(ans == 1e18) ans = -1;cout << ans << endl;}return 0;}