# 算法题：大于Y且数字总和等于X的最小数字

2021年4月8日17:43:03 发表评论 488 次浏览

## 本文概述

• 如果我们考虑从右数起的第(k + 1)位，并将其递增，那么k个最小有效数字的和有可能是[0,9k]范围内的任何数字。
• 找到这样的位置后, 请停止该过程并在该迭代中打印该数字。
• 如果k个最小有效数字有和M(其中0≤M≤9k)，则贪婪地得到答案:
• 从右向左遍历并插入9, 然后从数字总和中减去9。
• 一次, 总和小于9, 放置剩余的总和。

## C ++

``````//C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

//Function to return the minimum string
//of length d having the sum of digits s
string helper( int d, int s)
{

//Return a string of length d
string ans(d, '0' );

for ( int i = d - 1; i>= 0; i--) {

//Greedily put 9's in the end
if (s>= 9) {
ans[i] = '9' ;
s -= 9;
}

//Put remaining sum
else {
char c = ( char )s + '0' ;
ans[i] = c;
s = 0;
}
}

return ans;
}

//Function to find the smallest
//number greater than Y
//whose sum of digits is X
string findMin( int x, int Y)
{

//Convert number y to string
string y = to_string(Y);

int n = y.size();
vector<int> p(n);

//Maintain prefix sum of digits
for ( int i = 0; i <n; i++) {
p[i] = y[i] - '0' ;
if (i> 0)
p[i] += p[i - 1];
}

//Iterate over Y from the back where
//k is current length of suffix
for ( int i = n - 1, k = 0;; i--, k++) {

//Stores current digit
int d = 0;

if (i>= 0)
d = y[i] - '0' ;

//Increase current digit
for ( int j = d + 1; j <= 9; j++) {

//Sum upto current prefix
int r = (i> 0) * p[i - 1] + j;

//sum can be obtained in suffix
if (x - r>= 0 and x - r <= 9 * k) {

//Find suffix of length k
//having sum of digits x-r
string suf = helper(k, x - r);

string pre = "" ;
if (i> 0)
pre = y.substr(0, i);

//Append current character
char cur = ( char )j + '0' ;
pre += cur;

//Return the result
return pre + suf;
}
}
}
}

//Driver Code
int main()
{
//Given Number and Sum
int x = 18;
int y = 99;

//Function Call
cout <<findMin(x, y) <<endl;
return 0;
}``````

## C#

``````//C# program for the above approach
using System;
using System.Text;
using System.Collections;

class GFG{

//Function to return the minimum string
//of length d having the sum of digits s
static string helper( int d, int s)
{

//Return a string of length d
StringBuilder ans = new StringBuilder();

for ( int i = 0; i <d; i++)
{
ans.Append( "0" );
}

for ( int i = d - 1; i>= 0; i--)
{

//Greedily put 9's in the end
if (s>= 9)
{
ans[i] = '9' ;
s -= 9;
}

//Put remaining sum
else
{
char c = ( char )(s + ( int ) '0' );
ans[i] = c;
s = 0;
}
}
return ans.ToString();
}

//Function to find the smallest
//number greater than Y
//whose sum of digits is X
static string findMin( int x, int Y)
{

//Convert number y to string
string y = Y.ToString();

int n = y.Length;

ArrayList p = new ArrayList();

for ( int i = 0; i <n; i++)
{
}

//Maintain prefix sum of digits
for ( int i = 0; i <n; i++)
{
p[i] = ( int )(( int ) y[i] - ( int ) '0' );

if (i> 0)
{
p[i] = ( int )p[i] +
( int )p[i - 1];
}
}

//Iterate over Y from the back where
//k is current length of suffix
for ( int i = n - 1, k = 0;; i--, k++)
{

//Stores current digit
int d = 0;

if (i>= 0)
{
d = ( int ) y[i] - ( int ) '0' ;
}

//Increase current digit
for ( int j = d + 1; j <= 9; j++)
{
int r = j;

//Sum upto current prefix
if (i> 0)
{
r += ( int ) p[i - 1];
}

//sum can be obtained in suffix
if (x - r>= 0 && x - r <= 9 * k)
{

//Find suffix of length k
//having sum of digits x-r
string suf = helper(k, x - r);

string pre = "" ;

if (i> 0)
pre = y.Substring(0, i);

//Append current character
char cur = ( char )(j + ( int ) '0' );
pre += cur;

//Return the result
return pre + suf;
}
}
}
}

//Driver code
public static void Main( string [] arg)
{

//Given number and sum
int x = 18;
int y = 99;

//Function call
Console.Write(findMin(x, y));
}
}

//This code is contributed by rutvik_56``````

``189``