当前位置: 代码迷 >> 综合 >> 【贪心】[Atcoder Grand Contest 022]A Diverse Word
  详细解决方案

【贪心】[Atcoder Grand Contest 022]A Diverse Word

热度:29   发布时间:2023-09-27 07:45:13.0

题意:

定义一个完美的字符串表示为:字符串中没有出现两个相同的字符。
现在给出一个完美的字符串,求字典序比它大的最小的完美的字符串。
若没有输出-1


分析:

首先,如果给出的字符串长度不为26,那么直接在其后加入一个最小的没出现的字符,必然是字典序尽量小的。

再考虑长度已经为26的字符串,显然不能再加入字符了,只能将某个字符替换为在它后面的比它大的最小的字符,再将后面清空,就是最优的方案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 30
using namespace std;
char s[MAXN];
bool used[MAXN];
int main(){SF("%s",s);int len=strlen(s);for(int i=0;i<len;i++)used[s[i]-'a']=1;for(int i=0;i<26;i++)if(used[i]==0){PF("%s%c",s,i+'a');return 0;}for(int i=len-2;i>=0;i--){int minid=-1;for(int j=i+1;j<len;j++)if(s[j]>s[i]&&(minid==-1||s[minid]>s[j]))minid=j;if(minid!=-1){for(int j=0;j<i;j++)PF("%c",s[j]);PF("%c",s[minid]);return 0;}}PF("-1");
}
  相关解决方案