【备战秋招】每日一题:2022.10.27-数位和恰好为n的最大整数

为了更好的阅读体检，可以查看我的算法学习网
在线评测链接:P1017

题目内容

有一位名叫塔子哥的数学爱好者，他非常喜欢研究数字之间的规律和关系。

一天，他在研究正整数时，突然想到一个问题：如何找到一个最大的正整数，使得该正整数所有数位之和等于给定的正整数 $x$ ，且每个数位都不相等（任意一个数位不能是 $0$ ）？

塔子哥开始进行计算，并且思考了很长时间，但是他仍然找不到一个可行的解决方案。于是他决定向你寻求帮助，希望你能够帮助他解决这个问题。

输入描述

一个正整数 $x$ 。

$1\le x \le 100$

输出描述

如果不存在合法解，请输出 $- 1$ 。

否则输出最大的满足条件的正整数。

样例

输入

输出

题目思路

因为每个数位的数字都不能相等，因此凑出的正整数的长度不会超过9，所以可以枚举正整数的长度

贪心:

假设长度为i，则进行的操作为：从9到1选择数字，能选就选，直到选满i个，且每位之和为x。

选择时候需要判断选了这个数字后，之后能不能满足，

即：令s=x-sum_p , sum_p为前面选的数字之和，如选了当前最大的j，则判断s-j是否大于等于从1到剩下的位数的总和。
def check(s,cnt):
if s>=cnt*(cnt+1)//2:return True
return False
若能满足就选

代码

Python代码

def check(s,cnt):if s>=cnt*(cnt+1)//2:return Truereturn False
n=int(input())
ans=-1
for i in range(10):s,cnt=n,isum=0for j in range(9,0,-1):if s==0 or cnt==0:breakif check(s-j,cnt-1)==True:sum=sum*10+js-=jcnt-=1if s==0:ans=sum
print(ans)

Java代码

import java.util.Scanner;class Main {public static boolean check(int s, int cnt) {if (s >= cnt * (cnt - 1) / 2)return true;return false;}public static void main(String[] args) {int n, ans = -1;Scanner scanner = new Scanner(System.in);n = scanner.nextInt();for (int i = 0; i < 10; i++) {int s = n, cnt = i;int sum = 0;for (int j = 9; j > 0; j--) {if (s == 0 || cnt == 0)break;if (check(s - j, cnt - 1)) {sum = sum * 10 + j;s -= j;cnt--;}}if (s == 0)ans = sum;}System.out.println(ans);}
}

C++代码

#include <iostream>
#include <algorithm>
using namespace std;bool check(int s,int cnt){if (s>=cnt*(cnt-1)/2)return true;return false;
}
int main(){int n;cin>>n;int ans=-1;for (int i=0;i<10;i++){int s=n,cnt=i;int sum=0;for (int j=9;j>0;j--){if (s==0||cnt==0)break;if (check(s-j,cnt-1)){sum=sum*10+j;s-=j;cnt--;}}if (s==0)ans=sum;}cout<<ans<<endl;return 0;
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';process.stdin.on('data', (data) => {input += data;return;
});
process.stdin.on('end', () => {function check(s,cnt){if (s>=cnt*(cnt-1)/2)return true;return false;}var inputarray=input.split('\n');var n=Number(inputarray[0]),ans=-1;for (let i=0;i<10;i++){let s=n,cnt=i;let sum=0;for (let j=9;j>0;j--){if (s==0||cnt==0)break;if (check(s-j,cnt-1)){sum=sum*10+j;s-=j;cnt--;}}if (s==0)ans=sum;}console.log(ans);
});