题解 CF940C 【Phone Numbers】

TLMPEX · 2021-01-28 10:46:25 · 题解

这道题的主要思路就是贪心。

代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>

using namespace std;

const int maxn = 100005;
int n,k;
int vis[30];
char s[100005];
char ans[100005];

int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    for(int i=0;i<n;i++)
        vis[s[i]-'a']=1;
    if(k>n){
        printf("%s",s);
        for(int i=0;i<26;i++){
            if(vis[i]){
                int kk=k-n;
                while(kk--) 
                    printf("%c",i+'a');
                puts("");
                break;
            }
        }
    }
    else{
        strcpy(ans,s);
        ans[k]='\0';
        char Min='z';
        char Max='a';
        for(int i=0;i<26;i++){
            if(vis[i]){
                Min=i+'a';
                break;
            }
        }
        for(int i=25;i>=0;i--){
            if(vis[i]){
                Max=i+'a';
                break;
            }
        }
        for(int i=k-1;i>=0;i--){
            if(ans[i]!=Max){
                for(int j=ans[i]-'a'+1;j<26;j++){
                    if(vis[j]){
                        ans[i]=j+'a';
                        break;
                    }
                }
                printf("%s\n",ans);
                return 0;
            }
            else
                ans[i]=Min;
        }
        puts(ans);
    }
}