首页 > 试题广场 >

小红的正整数

[编程题]小红的正整数

热度指数：318 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正整数 $n$ ，请你找到最大的正整数，满足该正整数所有数位之和等于 $n$ ，且每个数位都不相等（每个数位不能是0）。
举个例子，如果 $n=7$ ，那么答案是421。因为4+2+1=7，且每个数位都不相等。

输入描述:

一个正整数。

输出描述:

如果不存在合法解，请输出-1。
否则输出最大的满足条件的正整数。

示例1

输入

输出

算法知识视频讲解

愉快的猕猴桃在泡池子

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

// n个点： * * * * * * * * *
// 先考虑一个衍生问题，把n个点分成尽量多的组，并且每个组分到的点数不相同，我们
//  要找出一种分法。
// dp[x][y]  x个点分成尽量多的组，每组点数不同，最大组点数为y，分出的最多组数。
/*
y=x   dp[x][x] = 1                                                                
y<x   dp[x][y] = 0     if max{i<y}(dp[x-y][i]) == 0           
                1+max{i<y}(dp[x-y][i])   if max{i<y}(dp[x-y][i]) != 0
y>x   dp[x][y] = 0                                                                
*/
//
int dp[102][102];

int main() {
    memset(dp, 0, sizeof(dp));
    int n;
    cin>>n;
    // 动态规划
    for(int x=1;x<=n;x++){
        for(int y=1;y<x;y++){
            int mx = 0;
            for(int i=1;i<y;i++){
                if(mx<dp[x-y][i])
                    mx = dp[x-y][i];
            }
            if(mx)
                dp[x][y] = mx + 1;
        }
        dp[x][x] = 1;
    }

    // 如果对于dp[n][1~9]均为0，则没有可行方案
    int mx_y = 0;
    for(int i=1;i<=9;i++){
        if(dp[n][mx_y]<dp[n][i])
            mx_y = i;
    }
    if(mx_y==0){
        cout<<-1;
        return 0;
    }

    // 否则重构出一个解。mx_y目前是能使分组数最多的分组方案中， 
        // 最大那个组的点数（当然我们只考虑范围1~9，更大的根本不考虑）
    vector<int> solution;
    int res = n-mx_y;
    solution.push_back(mx_y);
    while(res){
        int mx_yy = 0;
        for(int i=0;i<mx_y;i++)
            if(dp[res][mx_yy]<dp[res][i])
                mx_yy = i;
        mx_y = mx_yy;
        solution.push_back(mx_y);
        res-=mx_y;
    }

    // 为了得到原题的解，需要对我们衍生问题的解进行改进                                            |     |       |  |
    // 此时solution中就是分组的各组点数，降序排列。
        //  现在进一步改进，把点的差距拉开，重心尽量前移，
        //         例如：8  4  3 => 9  4  2 => 9 5 1
    int len = solution.size();
    int p = 0, q=len-1;
    int max_left=9,min_right=1;
    while(p!=q){
        if(solution[p]==max_left){
            max_left--;
            p++;
        }else if(solution[q]==min_right){
            min_right++;
            q--;
        }else{
            solution[p]++;
            solution[q]--;
        }
    }

    // 现在可以通过solution计算最终解
    int final = 0;
    for(int i:solution){
        final*=10;
        final+=i;
    }
    cout<<final;
    return 0;
}
// 64 位输出请用 printf("%lld")

编辑于 2023-04-26 15:44:42 回复(0)

牛客717689011号

递归
因为观察可以发现每个位数都有自己最大值最小值，比如如果最后答案是两位数，那两位数不重复，可以表达的最小值为3(结果是21)，最大值是最小三位数表达值-1，即(321)6-1为5。这样我们就可以发现一个规律，当一个数n要被分解成最大正整数，最高位必须要大，但是减去这个最高位，剩下的值，它的正整数的位数应该是原本位数减1，利用这个规律就可做递归运算了。

package main

import "fmt"

var m = make(map[int]int) //m保存位数信息
var use = make(map[int]bool) // use保存某一个数是否被使用过，保证不重复

func panduan(a int, wei int) (string, bool) {
	if a == 1 || a == 2 {
		return fmt.Sprintf("%d", a), true
	}
	res := ""
	for i := 9; i >= 1; i-- {
		if use[i] {
			continue
		}
		if a-i > 0 {
			as := a - i
			if m[as] == wei-1 {
				use[i] = true
				temp, ok := panduan(as, wei-1)
				if ok {
					res = fmt.Sprintf("%d%s", i, temp)
					return res, true
				} else {
					use[i] = false
				}
			}
		}
	}
	return "", false
}

func main() {
	// 读取一个int数字
	var a int
	fmt.Scan(&a)
	if a > 45 {
		fmt.Println(-1)
		return
	}
	if a == 45 {
		fmt.Println(987654321)
		return
	}
	for i := 1; i < 45; i++ {
		switch {
		case i == 1 || i == 2:
			m[i] = 1
		case i >= 3 && i < 6:
			m[i] = 2
		case i >= 6 && i < 10:
			m[i] = 3
		case i >= 10 && i < 15:
			m[i] = 4
		case i >= 15 && i < 21:
			m[i] = 5
		case i >= 21 && i < 28:
			m[i] = 6
		case i >= 28 && i < 36:
			m[i] = 7
		case i >= 36 && i < 45:
			m[i] = 8
		case i == 45:
			m[i] = 9
		}
	}
	res, ok := panduan(a, m[a])
	if ok {
		fmt.Println(res)
	} else {
		fmt.Println(-1)
	}
}

发表于 2023-04-18 12:46:09 回复(0)

牛客276102666号

n = int(input())

f=[]

for i in range(11):
    f.append([])
    for j in range(46):
        f[i].append(0)

if n>45:
    print(-1)
else:
    for i in range(1, 10):
        for j in range(0, n+1):
            f[i][j]=f[i-1][j]
            if (j>=i):
                bias = pow(10,len(str(f[i-1][j-i])))
                if f[i-1][j-i] == 0:
                    bias = 1
                f[i][j]=max(f[i][j],i*bias+f[i-1][j-i])

    print(f[9][n])

DP，不难发现，大数总是在小数之前出现，f[i][j]表示前i个数，和是j的最大表示。f[i][j]=max{f[i-1][j],concatenate(i,f[i-1][j-i])}

编辑于 2023-03-21 14:22:19 回复(0)

C/C++

牛客985204682号

#include <iostream>

#include<set>

#include <unordered_set>

#include <vector>

using namespace std;

int flag = 0; //判断是否已经找到，1为找到

void dfs(int index, int s, set<int>& v, int& flag) {

if (s == 0 || index > s || flag) {

return;

}

for (int i = index; i <= s && i <= 9; i++) {

//从小数到大数找可以保证在第一次满足的时候条件的时候是最大值

v.insert(i);

if (s - i == 0 && flag == 0) {

flag++;

return;

}

dfs(i + 1, s - i, v, flag);

if(flag==1) return; //找到答案后就不用去删除

v.erase(i);

}

}

int main() {

int n;

cin >> n;

if (n > (1 + 9) * 9 / 2) {

cout << -1;

return 0;

}

set<int>v;

int falg = 0;

dfs(1, n, v, flag);

int res = 0;

int help = 1;

for (auto& x : v) {

res += help * x;

help *= 10;

}

cout << res;

}

// 64 位输出请用 printf("%lld")

发表于 2023-03-18 15:33:58 回复(0)

尼古拉nicola

#include <iostream>

using namespace std;

//贪心:先计算是几位数，当前位始终选择可选的最大值，

int main() {

int hash[10] = {0, 1, 3, 6, 10, 15, 21, 28, 36, 45};

int n;

cin >> n;

if (n > 45) {

cout << -1;

return 0;

}

int bit = 9;

while (bit > 0) {

if (n >= hash[bit])

break;

--bit;

}

int num = 0, Max = 9;//Max 该位最大值

while (n && bit > 0) {

if (bit + n - hash[bit] < Max) {

Max = bit + n - hash[bit];

}

int cur=Max--;

num = num * 10 + cur;

n -= cur;

--bit;

}

cout << num;

}

发表于 2023-03-17 20:50:10 回复(2)

Java

S.I.R

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        if (n > 45) {
            System.out.println(-1);
            return;
        } else if (n < 3) {
            System.out.println(n);
            return;
        } else {
            int res = 0;
            ArrayList<Integer> nums = new ArrayList<>();
            int min = 1;
            int rest = 0;
            while (n != 0) {
                nums.add(min);
                n -= min;
                min++;
                if ((n - min) < (min + 1)) {
                   if (n<10 && n>0){
                       nums.add(n);
                   } else {
                       rest = n - 9;
                       nums.add(9);
                   } 
                    break;
                }
            }
            int times = 1;
            for (int i = nums.size() - 2; i >= 0; i--) {
                int cur = nums.get(i);
                if (rest <= 9 - times - cur) {
                    nums.set(i, cur + rest);
                    break;
                } else {
                    nums.set(i, 9 - times);
                    rest = rest - (9 - times - cur);
                    times++;
                }
            }
            for (int i = 0; i < nums.size(); i++) {
                res += nums.get(i) * Math.pow(10, i);
            }
            System.out.println(res);
        }
    }
}

维护状态，每次找到最小还原次数，然后向后向前遍历直到遇到0（Max_Value）

发表于 2023-03-16 16:22:46 回复(0)

梅老板的粉

递归

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int ret = -1;
void dfs(set<int>& cur, int i, int n, int sum) {
    if (i > 9) {
        if (sum == n) {
            int tmp = 0;
            for (auto it = cur.rbegin(); it != cur.rend(); ++it) {
                tmp = tmp * 10 + *it;
            }
            ret = max(ret, tmp);
        }
        return;
    }
    if (i+sum <= n) {
        cur.insert(i);
        dfs(cur, i+1, n, sum + i);
        cur.erase(i);
    }
    dfs(cur, i+1, n, sum);
}

int main() {
    int n;
    cin >> n;
    if (n > 45) {
        std::cout<<ret<<std::endl;
    }
    else {
        set<int> s;
        dfs(s, 1, n, 0);
        std::cout<<ret<<std::endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-03-16 01:31:36 回复(0)

wangjy520

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

vector<string> v;
string s = "";

void dfs(int i, int n, int sum) {
    if(i >= 10) {
        if(sum == n) {
            v.push_back(string(s));
        }
        return ;
    }
    if(sum > n) {
        return ;
    }
    if(n - sum > (i + 9) * (10 - i) / 2)
        return ;
    dfs(i + 1, n, sum);
    s += (i + '0');
    dfs(i + 1, n, sum + i);
    s.pop_back();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    if(n > 45) {
        cout << -1 << '\n';
        return 0;
    }
    dfs(1, n, 0);
    if(v.size() == 0) {
        cout << -1 << '\n';
    }
    else {
        sort(v[0].begin(), v[0].end(), greater<char>());
        string res = v[0];
        for(int i = 1;i < v.size();i++) {
            if(res.size() < v[i].size()) {
                sort(v[i].begin(), v[i].end(), greater<char>());
                res = v[i];
            }
            else if(res.size() == v[i].size()) {
                sort(v[i].begin(), v[i].end(), greater<char>());
                if(res.compare(v[i]) < 0) {
                    res = v[i];
                }
            }
        }
        cout << res << '\n';
    }
    
    
    return 0;
}

发表于 2023-03-07 12:06:30 回复(0)