【Educational Codeforces Round 36 C】 Permute Digits

在这里输入题意

【题解】

//从大到小枚举第i(1..len1)位
//剩余的数字从小到大排序。
//看看组成的数字是不是小于等于b
//如果是的话。
//说明第i位就是选这个数字了。
//接下来枚举下一位。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 20;

string s1,s2;

int len1,len2;

int bo[N],a[N],b[N];

vector<int> v,vans;

bool get_ans(){

    for (int i = 0;i <(int) vans.size();i++)

        v[i+1] = vans[i];

    int nn = (int) vans.size();

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

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

            v[++nn] = i;

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

        if (v[i]!=b[i] && v[i]>b[i]) return false;

        else if (v[i]!=b[i] && v[i]<b[i])return true;

    return true;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> s1 >> s2;

    len1 = s1.size(),len2 = s2.size();

    if (len1<len2){

        sort(s1.begin(),s1.end());

        reverse(s1.begin(),s1.end());

        cout <<s1<<endl;

        return 0;

    }

    v.resize(len1+1);

    //len1==len2;

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

        a[i+1] = s1[i]-'0';

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

        b[i+1] = s2[i]-'0';

    for (int i = 1;i <= len1;i++) bo[a[i]]++;

    bool haved = 0;

    for (int i = 0;i < len1;i++){

        for (int j = 9;j>=0;j--)

            if (bo[j]){

                int k = s2[i]-'0';

                if (j<=k || haved){

                    bo[j]--;

                    vans.push_back(j);

                    if (get_ans()){

                        if (j<k) haved =1;

                        break;

                    }

                    vans.pop_back();

                    bo[j]++;

                }

            }

    }

    for (int i = 0; i< (int) vans.size();i++)

        cout <<vans[i];

    //从大到小枚举第i(1..len1)位

    //剩余的数字从小到大排序。

    //看看组成的数字是不是小于等于b

    //如果是的话。

    //说明第i位就是选这个数字了。

    //接下来枚举下一位。

	return 0;

}

巴特西

【Educational Codeforces Round 36 C】 Permute Digits

最新文章

热门文章