题解：P13435 [GCJ 2009 #1B] The Next Number

yyycj · 2025-07-29 17:46:49 · 题解

题目简述

给你一个数字 K，求第一个大于 K 且其中与 K 共同含有的数位的个数必须相同。

主要思路

不难发现，如果我们用字符串读入 K，那么答案就是 next_permutation(K.begin(), K.end())；但如果 K 已经是最后一种排列，我们就应该将 K 加一位数而且使得它最小，那么加的就一定是 0。加的过程就需要先将 K 按升序排序，由于不能有前导零，所以需要将所有的前导零挪到最高且不是 0 的数位后面，并再多加一个 0。

AC Code

#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
template<typename T> void read(T &x) { int f = 1; x = 0; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }x *= f; }
template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
template<typename T> void print(T x) { if (x < 0) { putchar('-'); x = -x; }if (x > 9) { print(x / 10); }putchar(char(x % 10 + 48)); }
template<typename T, typename ...Args> void print(T x, Args ...args) { print(x); putchar(' '); print(args...); }

typedef long long ll;
typedef long double db;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T1, typename T2> ll _pow(T1 a, T2 b) { ll x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------

// ----------------------------

int main() {
    int t; read(t);
    // ----------------------------
    int cnt;
    string k;
    for (int i = 1; i <= t; i++) {
        cin >> k;
        cout << "Case #" << i << ": ";
        if (next_permutation(k.begin(), k.end())) cout << k << '\n';
        else {  // 如果当前序列是最后一个排列，next_permutation 会返回 false
            sort(k.begin(), k.end());
            reverse(k.begin(), k.end());  // 为了判断前导零且高效，现将 k 翻转，利用 string 的 pop_back() 函数去掉前导零
            cnt = 0;
            while (k.back() == '0') {
                cnt++;
                k.pop_back();
            }
            cout << k.back(); k.pop_back();  // 先输出最高且不是 0 的数位
            for (int j = 1; j <= cnt + 1; j++) cout << 0;  // 为了增加一位多输出一个 0
            reverse(k.begin(), k.end());  // 不要忘了翻转再将剩下的全部输出
            cout << k << '\n';
        }
    }
    // ----------------------------

    return 0;
}