题解

题面描述

给定两个数列

• 数列$s_1$由若干个非负整数（每个数字范围为$0\sim9$，注意$s_1$可能包含$0$）构成，
• 数列$s_2$同样由非负整数组成。

可以对数列$s_1$进行任意次操作，每次操作可交换其中任意两个数字的位置，也就是说可以任意排列数列$s_1$中的数字。目标是让排列后的$s_1$构成的数字最大，但同时必须严格小于数列$s_2$构成的数字。如果不存在满足条件的排列，则输出$-1$。

思路

1. 长度判断

   • 如果$n<m$：由于$s_1$拼成的数字位数较少，直接将$s_1$中的数字降序排列即可得到最大数字（此时无论如何排列都比$s_2$短，必然小于$s_2$）。
   • 如果$n>m$：排列后数字的位数严格大于$s_2$，必然大于$s_2$，输出$-1$。
   • 当$n=m$时，需要构造一个排列使得结果既尽可能大又严格小于$s_2$。

2. 贪心＋回溯（仅讨论$n=m$情况）

   • 从最高位（位置$i=0$）开始遍历。在每一位，优先考虑跟$s_2[i]$相同的数字以保持前缀一致；如果后续无法构造出合法排列，则回溯到上一位，尝试选择小于原来选择的数字。
   • 在考虑当前位置时，遍历可选数字时要考虑$0$，即从$9$到$0$（不排除$0$）。
   • 当选择的数字$d$满足$d<s_2[i]$时，后续剩余位直接填入当前剩余数字的降序排列即可，因为此时不论怎么填充最终数字必然小于$s_2$。

3. 核心问题
   本质上是：在给定数字频率下，构造出最大但严格小于目标数$s_2$的排列。利用“贪心匹配前缀+必要时回溯”的策略，并在每个位置尝试包括$0$在内的所有数字。

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
// 根据当前剩余数字频率，构造尾部数字的降序排列字符串（包括数字0）
string fillDescending(vector<int> cnt) {
    string res = "";
    for (int d = 9; d >= 0; d--) {
        while (cnt[d] > 0) {
            res.push_back('0' + d);
            cnt[d]--;
        }
    }
    return res;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        string s1, s2;
        cin >> s1 >> s2;
 
        // 如果 s1 的数字个数小于 s2，直接降序排列 s1 即可
        if(n < m){
            sort(s1.begin(), s1.end(), greater<char>());
            cout << s1 << "\n";
            continue;
        }
 
        // 如果 s1 数字个数大于 s2，则不可能得到一个小于 s2 的数字
        if(n > m){
            cout << -1 << "\n";
            continue;
        }
 
        // 构造 s1 中数字的频率，注意数字范围为0~9
        vector<int> cnt(10, 0);
        for(char ch : s1){
            cnt[ch - '0']++;
        }
 
        // ans 用于保存答案构造过程，长度为 n 的数组
        vector<int> ans(n, -1);
 
        // backup 保存每一步选择后的剩余数字状态，便于回溯
        vector<vector<int>> backup(n);
 
        int i = 0; // 当前处理位置
        bool found = false;
        while(i >= 0){
            // 若已填满所有位，则说明结果与 s2 完全相同，需回溯修改
            if(i == n) {
                i--; 
            }
 
            // 若当前位置已有选取，则恢复其对应的数字频率
            if(ans[i] != -1){
                cnt[ ans[i] ]++;
            }
 
            // 当前尝试数字的起始值：若本位置未做选择，从 s2[i] 开始；否则从上一次选择的数字减1开始
            int start;
            if(ans[i] == -1) start = s2[i] - '0';
            else start = ans[i] - 1;
 
            // 清除当前位置的选择
            ans[i] = -1;
 
            // 在当前位置尝试从 start 到 0 的数字，选择最大的合适数字
            bool success = false;
            for(int d = start; d >= 0; d--){
                if(cnt[d] > 0){
                    // 若选择的数字 d 小于 s2[i]，则后续直接填入剩余数字降序排列
                    if(d < s2[i] - '0'){
                        ans[i] = d;
                        cnt[d]--;
                        string tail = fillDescending(cnt);
                        // 构造答案字符串，前部分为 ans[0..i]，后接 tail
                        string result = "";
                        for (int j = 0; j <= i; j++){
                            result.push_back('0' + ans[j]);
                        }
                        result += tail;
                        cout << result << "\n";
                        found = true;
                        break;
                    }
                    else { // d 等于 s2[i]
                        ans[i] = d;
                        cnt[d]--;
                        // 保存当前剩余状态以便后续回溯
                        backup[i] = cnt;
                        success = true;
                        break;
                    }
                }
            }
            if(found) break;
 
            // 若在当前位置未找到合适的数字，则回溯修改上一位
            if(!success){
                ans[i] = -1;
                i--;
                if(i < 0){
                    cout << -1 << "\n";
                    break;
                }
                // 恢复上一位的状态
                cnt = backup[i];
            }
            else{
                i++;
                // 如果已经填满所有位，说明构造出的数字与 s2 完全相同，
                // 为满足严格小于 s2，再回溯最后一位
                if(i == n){
                    i--;
                }
            }
        }
    }
    return 0;
}

Python

# -*- coding: utf-8 -*-
def fill_descending(cnt):
    # 根据当前剩余数字频率构造降序排列字符串（包括数字0）
    res = []
    for d in range(9, -1, -1):
        res.extend([str(d)] * cnt[d])
    return "".join(res)

def main():
    import sys
    input = sys.stdin.readline
    T = int(input().strip())
    for _ in range(T):
        n_m = input().split()
        if not n_m: 
            n_m = input().split()
        n, m = map(int, n_m)
        s1 = input().strip()
        s2 = input().strip()
        
        if n < m:
            # 如果 s1 长度小于 s2，直接降序排列 s1
            ans = ''.join(sorted(s1, reverse=True))
            print(ans)
            continue
        if n > m:
            # 如果 s1 长度大于 s2，则不可能构成小于 s2 的数字
            print(-1)
            continue

        # 构造数字频率，注意范围为 0 到 9
        cnt = [0] * 10
        for ch in s1:
            cnt[int(ch)] += 1

        ans = [-1] * n  # 保存答案数字，数组每个位置保存选择的数字
        # backup 保存每个位置选择后剩余数字的状态，便于回溯
        backup = [None] * n
        
        i = 0  # 当前处理位置
        found = False
        while i >= 0:
            if i == n:
                # 如果 i == n，则所有位已确定，构造的数字与 s2 相同，
                # 需要回溯来调整最后一位
                i -= 1
            if ans[i] != -1:
                cnt[ans[i]] += 1  # 恢复当前位置之前的选择
            # 当前尝试数字的起始值
            if ans[i] == -1:
                start = int(s2[i])
            else:
                start = ans[i] - 1
            ans[i] = -1  # 清除当前位置选择
            success = False
            for d in range(start, -1, -1):
                if cnt[d] > 0:
                    if d < int(s2[i]):
                        # 当前位选择数字小于 s2[i]，后续直接填入剩余数字降序排列
                        ans[i] = d
                        cnt[d] -= 1
                        tail = fill_descending(cnt)
                        result = "".join(str(num) for num in ans[:i+1]) + tail
                        print(result)
                        found = True
                        break
                    else:
                        # 选择与 s2[i] 相等，保持前缀一致进入下一位
                        ans[i] = d
                        cnt[d] -= 1
                        backup[i] = cnt.copy()
                        success = True
                        break
            if found:
                break
            if not success:
                ans[i] = -1
                i -= 1
                if i < 0:
                    print(-1)
                    break
                cnt = backup[i].copy()
            else:
                i += 1
                if i == n:
                    # 若填满所有位，构造出的数字与 s2 完全相同，
                    # 需要回溯修改最后一位
                    i -= 1

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    // 根据当前剩余数字频率构造降序排列的字符串（包括数字0）
    static String fillDescending(int[] cnt) {
        StringBuilder sb = new StringBuilder();
        for (int d = 9; d >= 0; d--) {
            while (cnt[d] > 0) {
                sb.append(d);
                cnt[d]--;
            }
        }
        return sb.toString();
    }
    
    public static void main(String[] args)throws IOException{
        // 使用 BufferedReader 以提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder output = new StringBuilder();
        while(T-- > 0){
            String[] nm = br.readLine().trim().split("\\s+");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            String s1 = br.readLine().trim();
            String s2 = br.readLine().trim();
            
            // 若 s1 长度小于 s2，直接对 s1 降序排列即可
            if(n < m){
                char[] arr = s1.toCharArray();
                Arrays.sort(arr);
                StringBuilder rev = new StringBuilder(new String(arr)).reverse();
                output.append(rev.toString()).append("\n");
                continue;
            }
            // 若 s1 长度大于 s2，则无法构造出小于 s2 的数字
            if(n > m){
                output.append("-1\n");
                continue;
            }
            
            // 统计 s1 中各数字的频率，数字范围为 0 到 9
            int[] cnt = new int[10];
            for (int i = 0; i < s1.length(); i++){
                cnt[s1.charAt(i) - '0']++;
            }
            
            // ans 保存答案构造过程
            int[] ans = new int[n];
            Arrays.fill(ans, -1);
            
            // backup 用于保存每一步选择后剩余数字频率，便于回溯
            int[][] backup = new int[n][];
            
            int i = 0; // 当前处理位置
            boolean found = false;
            while(i >= 0){
                if(i == n) {
                    // 若所有位已填，构造数字与 s2 相同，需要回溯调整
                    i--;
                }
                // 恢复当前位置的选择（若已有选择）
                if(ans[i] != -1){
                    cnt[ans[i]]++;
                }
                int start;
                if(ans[i] == -1) {
                    start = s2.charAt(i) - '0';
                } else {
                    start = ans[i] - 1;
                }
                ans[i] = -1; // 清除当前位置的选择
                boolean success = false;
                for(int d = start; d >= 0; d--){
                    if(cnt[d] > 0){
                        if(d < s2.charAt(i) - '0'){
                            // d 小于 s2[i]，后续直接填入剩余数字降序排列即可
                            ans[i] = d;
                            cnt[d]--;
                            String tail = fillDescending(cnt);
                            StringBuilder result = new StringBuilder();
                            for(int j = 0; j <= i; j++){
                                result.append(ans[j]);
                            }
                            result.append(tail);
                            output.append(result.toString()).append("\n");
                            found = true;
                            break;
                        } else {
                            // d 等于 s2[i]，保持前缀一致进入下一位
                            ans[i] = d;
                            cnt[d]--;
                            backup[i] = cnt.clone();
                            success = true;
                            break;
                        }
                    }
                }
                if(found) break;
                if(!success){
                    ans[i] = -1;
                    i--;
                    if(i < 0){
                        output.append("-1\n");
                        break;
                    }
                    cnt = backup[i].clone();
                } else {
                    i++;
                    if(i == n){
                        // 若填满所有位后结果与 s2 相等，需要回溯修改
                        i--;
                    }
                }
            }
        }
        System.out.print(output.toString());
    }
}

题目内容

多多有两个仅由正整数构成的数列$s_1$和$s_2$,多多可以对$s_1$进行任意次操作,每次操作可以置换$s_1$中任意两个数字的位置.

多多想让数列$s_1$构成的数字尽可能大,但是小于$s_2$

请问再经过任意次操作后,满足上述条件的数列$s_1$构成的数字是多少.

输入描述

第一行,包含一个正整数$T(1≤T≤10)$代表测试数据的组数.

对于每组测试数据,分别有三行:

第一行,有两个正整数$n(1≤n≤10^5)$, $m(1≤m≤10^5)$,分别表示数列$s_1$和$s_2$的长度.

第二行,有一行仅由正整数组成的的长度为$n$数列$s_1$

第三行，有一行仅由正整数组成的的长度为$m$数列$s_2$

输出描述

对于每组数据,输出数列$s_1$在经过任意次置换操作后,得到的满足条件的最大值数字

如果不存在这样的数字,则输出$-1$

样例1

输入

3
5 5
12345
45678
5 5
65479
54231
5 5
42315
12345

输出

45321
49765
-1