UVa 146 ID Codes

题目描述

在2084 20842084年，政府为了加强对公民的控制并应对长期存在的法律与秩序问题，决定采取一项激进措施：为每位公民在左手腕植入一个微型计算机。该计算机存储个人身份信息，并包含发射器以便中央计算机追踪和监控人员的位置。

每个计算机的核心部分是一个唯一的身份识别码，最多由50 5050个字符组成，这些字符来自 26 个小写字母。任意给定的识别码所使用的字符集是随机选定的。生产识别码的复杂过程使得制造商更容易生产那些仅对已有字符进行重排的新识别码，而不是生成包含不同字母集合的全新识别码。因此，一旦选定一组字母，就会先将所有可能的排列使用完毕，然后再更换字母集合。

例如，假设某个识别码包含3 33个a、2 22个b和1 11个c，那么在这些条件下，允许的60 6060个识别码中的三个按字典序从上到下依次是：

abaabc abaabc abaabc

题目要求编写程序，帮助生成这些识别码的后继（下一个字典序的识别码）。程序接收一个长度不超过50 5050的字符串（可能包含重复字符），输出该字符串对应字符集合的字典序后继，如果已经是最后一个，则输出No Successor。

输入与输出格式

输入
输入包含多行，每行一个字符串表示一个识别码，以单独一行#结束。

输出
对于每个输入的识别码，输出其后继识别码或No Successor。

样例输入

abaabc cbaba #

样例输出

ababac No Successor

解题思路

本题的核心任务是求一个给定字符串的字典序下一个排列。如果当前排列已是该字符集合所能构成的最大字典序排列，则输出No Successor。

排列生成算法

字符串的“下一个排列”可以用标准的“下一个排列算法”来求解，该算法步骤如下：

1. 从右向左扫描，找到第一个满足s[i] < s[i + 1]的位置i ii。如果找不到这样的i ii，说明整个序列是降序排列的，也就是字典序最大，没有后继。
2. 从右向左扫描，找到第一个满足s[j] > s[i]的位置j jj。
3. 交换s[i]和s[j]。
4. 将位置i ii之后的子串反转（即变为升序排列）。

该算法的时间复杂度为O ( n ) O(n)O(n)，其中n nn为字符串长度（本题n ≤ 50 n \leq 50n≤50）。

使用标准库函数

在C++ \texttt{C++}C++中，<algorithm>库提供了next_permutation函数，可以直接对字符串或容器求出下一个排列。如果已经是最后一个排列，该函数返回false，否则返回true并修改容器内容为下一个排列。

本题特殊之处

虽然题目描述中提到了字符集合的概念，但实际上我们只需要对输入字符串本身求下一个排列即可。因为next_permutation会自动处理重复字符和字典序逻辑，得到的就是该字符集合的下一个识别码。

代码实现

// ID Codes// UVa ID: 146// Verdict: Accepted// Submission Date: 2016-01-22// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){string line;while(getline(cin,line),line!="#"){if(next_permutation(line.begin(),line.end()))cout<<line<<endl;elsecout<<"No Successor"<<endl;}return0;}

复杂度分析

• 时间复杂度：每次调用next_permutation为O ( n ) O(n)O(n)，其中n nn是字符串长度。
• 空间复杂度：O ( n ) O(n)O(n)，用于存储字符串。

总结

本题是一个典型的“下一个排列”问题，适合用来练习排列生成算法或熟悉标准库的使用。使用C++ \texttt{C++}C++的next_permutation可以简洁高效地解决问题，无需手动实现排列生成逻辑。注意特殊情况——当输入字符串已经是最大字典序时，输出No Successor。