AT3724 Two Anagrams

    • 47通过
    • 112提交
  • 题目来源 AtCoder 3724
  • 评测方式 RemoteJudge
  • 标签 字符串 排序 贪心
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定$2$个字串($\color{blue}\text{长度<100}\color{red}\text{可能有空格}$),判断是否可以通过排序这$2$个串使得$\color{purple}\text{第一个串<第二个串}\color{red}\text{(指的是字典序!)}$

    题目描述

    英小文字のみからなる文字列 $ s $ , $ t $ が与えられます。 あなたは、 $ s $ の文字を好きな順に並べ替え、文字列 $ s' $ を作ります。 また、 $ t $ の文字を好きな順に並べ替え、文字列 $ t' $ を作ります。 このとき、辞書順で $ s'\ <\ t' $ となるようにできるか判定してください。

    输入输出格式

    输入格式:

    Input is given from Standard Input in the following format:

     $ s $ 
     $ t $ 

    输出格式:

    If it is possible to satisfy $ s'\ <\ t' $ , print Yes; if it is not, print No.

    输入输出样例

    输入样例#1: 复制
    yx
    axy
    输出样例#1: 复制
    Yes
    输入样例#2: 复制
    ratcode
    atlas
    输出样例#2: 复制
    Yes
    输入样例#3: 复制
    cd
    abc
    输出样例#3: 复制
    No
    输入样例#4: 复制
    w
    ww
    输出样例#4: 复制
    Yes
    输入样例#5: 复制
    zzz
    zzz
    输出样例#5: 复制
    No
    输入样例#6: 复制
    yx
    axy
    输出样例#6: 复制
    Yes
    输入样例#7: 复制
    ratcode
    atlas
    输出样例#7: 复制
    Yes
    输入样例#8: 复制
    cd
    abc
    输出样例#8: 复制
    No
    输入样例#9: 复制
    w
    ww
    输出样例#9: 复制
    Yes
    输入样例#10: 复制
    zzz
    zzz
    输出样例#10: 复制
    No

    说明

    注釈

    長さ $ N $ の文字列 $ a\ =\ a_1\ a_2\ ...\ a_N $ および長さ $ M $ の文字列 $ b\ =\ b_1\ b_2\ ...\ b_M $ について、辞書順で $ a\ <\ b $ であるとは、次の $ 2 $ つの条件のいずれかが成り立つことをいう;

    • $ N\ <\ M $ かつ $ a_1\ =\ b_1 $ , $ a_2\ =\ b_2 $ , ..., $ a_N\ =\ b_N $ である。
    • ある $ i $ ( $ 1\ \leq\ i\ \leq\ N,\ M $ ) が存在して、 $ a_1\ =\ b_1 $ , $ a_2\ =\ b_2 $ , ..., $ a_{i\ -\ 1}\ =\ b_{i\ -\ 1} $ かつ $ a_i\ <\ b_i $ である。 ただし、文字どうしはアルファベット順で比較される。

    例えば、xy $ < $ xya であり、atcoder $ < $ atlas である。

    制約

    • $ s $ , $ t $ の長さは $ 1 $ 以上 $ 100 $ 以下である。
    • $ s $ , $ t $ は英小文字のみからなる。

    Problem Statement

    You are given strings $ s $ and $ t $ , consisting of lowercase English letters. You will create a string $ s' $ by freely rearranging the characters in $ s $ . You will also create a string $ t' $ by freely rearranging the characters in $ t $ . Determine whether it is possible to satisfy $ s'\ <\ t' $ for the lexicographic order.

    Notes

    For a string $ a\ =\ a_1\ a_2\ ...\ a_N $ of length $ N $ and a string $ b\ =\ b_1\ b_2\ ...\ b_M $ of length $ M $ , we say $ a\ <\ b $ for the lexicographic order if either one of the following two conditions holds true:

    • $ N\ <\ M $ and $ a_1\ =\ b_1 $ , $ a_2\ =\ b_2 $ , ..., $ a_N\ =\ b_N $ .
    • There exists $ i $ ( $ 1\ \leq\ i\ \leq\ N,\ M $ ) such that $ a_1\ =\ b_1 $ , $ a_2\ =\ b_2 $ , ..., $ a_{i\ -\ 1}\ =\ b_{i\ -\ 1} $ and $ a_i\ <\ b_i $ . Here, letters are compared using alphabetical order.

    For example, xy $ < $ xya and atcoder $ < $ atlas.

    Constraints

    • The lengths of $ s $ and $ t $ are between $ 1 $ and $ 100 $ (inclusive).
    • $ s $ and $ t $ consists of lowercase English letters.

    Sample Explanation 1

    例えば、yxxy と並べ替え、axyyxa と並べ替えれば、xy $ < $ yxa となります。

    Sample Explanation 2

    例えば、ratcodeacdeort と並べ替え、atlastslaa と並べ替えれば、acdeort $ < $ tslaa となります。

    Sample Explanation 3

    cd, abc をそれぞれどのように並べ替えても、目標を達成できません。

    Sample Explanation 6

    We can, for example, rearrange yx into xy and axy into yxa. Then, xy $ < $ yxa.

    Sample Explanation 7

    We can, for example, rearrange ratcode into acdeort and atlas into tslaa. Then, acdeort $ < $ tslaa.

    Sample Explanation 8

    No matter how we rearrange cd and abc, we cannot achieve our objective.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。