解题思路

  1. 题目要求构造一个十进制数,使得:
    • 数位和等于给定值
    • 相邻数位不能相同
    • 不能包含
    • 这个数要尽可能大
  2. 关键发现:
    • 要使数尽可能大,应该使用尽可能大的数字
    • 由于相邻数位不能相同,最优解应该是交替使用两个数字
    • 9和8太大,无法构造出大多数 值,最优解应该使用1和2交替
  3. 根据 的值分三种情况:
    • 能被3整除:使用"21"重复
    • 除以3余1:使用"12"重复,最后加"1"
    • s除以3余2:使用"21"重复,最后加"2"

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int s;
    cin >> s;
    
    string result;
    if (s % 3 == 0) {
        int pairs = s / 3;
        for (int i = 0; i < pairs; i++) {
            result += "21";
        }
    } else if (s % 3 == 1) {
        int pairs = (s - 1) / 3;
        for (int i = 0; i < pairs; i++) {
            result += "12";
        }
        result += "1";
    } else {  // s % 3 == 2
        int pairs = (s - 2) / 3;
        for (int i = 0; i < pairs; i++) {
            result += "21";
        }
        result += "2";
    }
    
    cout << result << endl;
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        
        StringBuilder result = new StringBuilder();
        if (s % 3 == 0) {
            int pairs = s / 3;
            for (int i = 0; i < pairs; i++) {
                result.append("21");
            }
        } else if (s % 3 == 1) {
            int pairs = (s - 1) / 3;
            for (int i = 0; i < pairs; i++) {
                result.append("12");
            }
            result.append("1");
        } else {  // s % 3 == 2
            int pairs = (s - 2) / 3;
            for (int i = 0; i < pairs; i++) {
                result.append("21");
            }
            result.append("2");
        }
        
        System.out.println(result);
    }
}
s = int(input())

result = ""
if s % 3 == 0:
    pairs = s // 3
    result = "21" * pairs
elif s % 3 == 1:
    pairs = (s - 1) // 3
    result = "12" * pairs + "1"
else:  # s % 3 == 2
    pairs = (s - 2) // 3
    result = "21" * pairs + "2"

print(result)

算法及复杂度

  • 算法:贪心构造
  • 时间复杂度: - 需要构造长度正比于 的字符串
  • 空间复杂度: - 需要存储构造的结果字符串