Largest Beautiful Number CodeForces

题意：给定一个长度为偶数的数，输出小于它的最大的美丽数。如果一个数长度为偶数，且没有前导零，并存在一种排列是回文数的数为美丽数。给定的t个数长度总和不超过200000.

分析：

1、存在一种排列为回文数，即这个数包含的数字都是偶数个。

2、预处理出每个数字的个数。

3、从最右边一位依次往左枚举，当逐渐减小第i位时，统计目前的数中，第i位之前有多少个数字是奇数个，记为cnt。

4、因为第i位之后的数字可以随便填，所以如果第i位之后数字的个数大于等于cnt，那么则可以得出答案，大于的部分先用9填充，再从大到小依次用奇数个的数字填充即可。

5、如果枚举到最左边也没有答案，则直接输出数字长度-2个9即可。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 200000 + 10;

char s[MAXN];

map<int, int> mp;

int len;

vector<int> v;

bool judge(){

    for(int i = len - 1; i >= 0; --i){

        int t;

        if(i == 0) t = 1;

        else t = 0;

        --mp[s[i] - '0'];

        for(int j = s[i] - '0' - 1; j >= t; --j){

            ++mp[j];

            v.clear();

            for(int k = 0; k < 10; ++k){

                if(mp[k] & 1){

                    v.push_back(k);

                }

            }

            int l = v.size();

            if(l <= len - i - 1){

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

                    printf("%c", s[k]);

                }

                printf("%d", j);

                for(int k = 0; k < len - i - 1 - l; ++k){

                    printf("9");

                }

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

                for(int k = l - 1; k >= 0; --k){

                    printf("%d", v[k]);

                }

                printf("\n");

                return true;

            }

            --mp[j];

        }

    }

    return false;

}

int main(){

    int t;

    scanf("%d", &t);

    while(t--){

        mp.clear();

        scanf("%s", s);

        len = strlen(s);

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

            ++mp[s[i] - '0'];

        }

        if(!judge()){

            for(int i = 0; i < len - 2; ++i){

                printf("9");

            }

            printf("\n");

        }

    }

    return 0;

}

巴特西

Largest Beautiful Number CodeForces - 946E （贪心）

最新文章

热门文章