Codeforces 670F - Restore a Number - [字符串]

题目链接：https://codeforces.com/contest/670/problem/F

题意：

有一个非负整数 $n$，在它的右侧添上它的位数后，被发送出去；例如 $6510$，加上位数 $4$，变成 $65104$，发送出去。

但是，接受者接收到的数字则是被打乱了的，例如接收到了 $01465$，发送者只知道其中一段数字是什么，例如知道原数字中有一段是 $51$。

要你根据已知的信息推测出可能的 $n$ 中最小的那个。

题解：

首先在大约 $O(n)$ 的时间复杂度下可以知道这个数字是 $k$ 位。

然后，我们可以知道这个数字是由 $c_0$ 个 $0$、$c_1$ 个 $1$、……、$c_9$ 个 $9$，以及一段给定的一段数字 $t$ 组成的。

我们要考虑如何找出最小的那个，不妨考虑如下可能的情况：

1、$t$ + $c_0$ 个 $0$ + …… + $c_9$ 个 $9$。

2、在 $1 \sim 9$ 找一个最小的打头，剩下的依旧按照若干个 $0$ + …… + 若干个 $9$ 排列，其中 $t$ 按照 $t[0]$ 是什么，插在那个数的左侧或者右侧；例如 $10022599$，而 $t = [223]$，则有可能是答案的是 $100[223]22599$ 或者 $10022[223]599$；另一种例子是 $1089$，$t = [63]$，则可能是答案的是 $10[63]89$。

答案只可能是以上这些情况中的一种。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int SIZE=1e6+;

char s[SIZE],t[SIZE];

int slen,tlen;

int cnt_s[],cnt_t[];

int digit()

{

    int dgt;

    vector<int> v;

    for(dgt=tlen;dgt<=slen;dgt++)

    {

        int tp[]={}, k=dgt;

        while(k) ++tp[k%], k/=;

        bool ok=;

        for(int i=;i<;i++) if(cnt_t[i]+tp[i]>cnt_s[i]) ok=;

        int sum=;

        for(int i=;i<;i++) sum+=cnt_s[i]-tp[i];

        if(sum!=dgt) ok=;

        if(ok)

        {

            for(int i=;i<;i++) cnt_s[i]-=cnt_t[i]+tp[i];

            return dgt;

        }

    }

}

bool check(const string& s) //检查前导零

{

    if(s.size()> && s[]=='') return ;

    else return ;

}

int main()

{

    ios::sync_with_stdio();

    cin.tie(), cout.tie();

    cin>>s>>t;

    slen=strlen(s), tlen=strlen(t);

    for(int i=;i<slen;i++) cnt_s[s[i]-'']++;

    for(int i=;i<tlen;i++) cnt_t[t[i]-'']++;

    int dgt=digit();

    string res1,res2,res3;

    res1=t;

    for(int i=;i<;i++)

    {

        for(int j=;j<=cnt_s[i];j++)

        {

            res1+=(char)(''+i);

        }

    }

    for(int i=;i<;i++)

    {

        if(cnt_s[i]>)

        {

            res2+=(char)(''+i);

            res3+=(char)(''+i);

            cnt_s[i]--;

            break;

        }

    }

    for(int i=;i<;i++)

    {

        if(t[]-''==i) res2+=(string)t;

        while(cnt_s[i]>)

        {

            res2+=(char)(''+i);

            res3+=(char)(''+i);

            cnt_s[i]--;

        }

        if(t[]-''==i) res3+=(string)t;

    }

    string ans;

    if(!check(res1)) ans=(ans.size()?min(ans,res1):res1);

    if(!check(res2)) ans=(ans.size()?min(ans,res2):res2);

    if(!check(res3)) ans=(ans.size()?min(ans,res3):res3);

    cout<<ans<<'\n';

}