题解归档 - cf915C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf915C
• 本地来源：problems/cf915C/idea.md
• 题目链接：https://codeforces.com/contest/915/problem/C
• 原始标题：915C Permute Digits

思路

915C Permute Digits

题意

将整数 a 的各位重排，得到不超过 b 的最大数；输出长度与 a 相同，不能有前导零。保证有解。

思路

1. |a| < |b|：任意重排都 ≤ b（数值意义），直接降序排列 a 的各位。
2. |a| = |b|：从左到右贪心填位；若当前位取 < b[i] 的数字，后面填剩余数字降序即可；若必须与 b[i] 相等则继续；若当前位无法放置则回溯一位，换更小数字重试。

注意：同长度才能用字符串比较；比较「是否 ≤ b」时若长度不同要先比位数。

复杂度

位数 ≤ 19，每位最多回溯常数次，实际 O(19×10)。

验证

官方样例 3 组 + Kali 对拍 brute.cpp（全排列，gen 长度 ≤ 7）500 组通过。

结论

Educational R36 C，贪心 + 回溯；待提交。

代码

来源：problems/cf915C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:32:48
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string as,bs,ans;
ll cnt[12],n,i,j,k,zc,pd,cur,dq;
int main(){
    cin>>as>>bs;
    n=as.size();
    for(i=0;i<n;i++) cnt[as[i]-'0']++;
    if(n<(ll)bs.size()){
        for(j=9;j>=0;j--)
            while(cnt[j]--) ans+=(char)('0'+j);
        cout<<ans<<"\n";
        return 0;
    }
    i=0;
    while(i<n){
        pd=0;
        for(j=9;j>=0;j--){
            if(cnt[j]==0) continue;
            if(i==0 and j==0) continue;
            if(j<bs[i]-'0'){
                cnt[j]--;
                ans+=(char)('0'+j);
                for(k=9;k>=0;k--)
                    while(cnt[k]--) ans+=(char)('0'+k);
                cout<<ans<<"\n";
                return 0;
            }
            if(j==bs[i]-'0'){
                cnt[j]--;
                ans+=(char)('0'+j);
                pd=1;
                i++;
                break;
            }
        }
        if(!pd){
            zc=ans.back()-'0';
            cnt[zc]++;
            ans.pop_back();
            i--;
            pd=0;
            for(j=zc-1;j>=0;j--){
                if(cnt[j]==0) continue;
                if(i==0 and j==0) continue;
                cnt[j]--;
                ans+=(char)('0'+j);
                if(j<bs[i]-'0'){
                    for(k=9;k>=0;k--)
                        while(cnt[k]--) ans+=(char)('0'+k);
                    cout<<ans<<"\n";
                    return 0;
                }
                if(j==bs[i]-'0'){
                    i++;
                    pd=1;
                }
                break;
            }
            if(!pd and i==0) break;
        }
    }
    cout<<ans<<"\n";
    return 0;
}