题解：Wordfish密码生成问题（POJ3359/UVA1209/LA3173）

一、题目分析

本题要求根据给定的用户名生成特定密码，密码规则如下：

1. 从用户名的21个连续字典序排列中选择（中间排列为原用户名）。
2. 选择相邻字符绝对差的最小值最大的排列。
3. 若有多个排列满足条件，选择字典序最小的排列。

二、核心思路

1. 生成排列：使用prev_permutation和next_permutation生成原用户名前后各10个排列，共21个。
2. 计算最小绝对差：对每个排列，计算相邻字符的绝对差，并找出最小值。
3. 排序选择最优解：按最小绝对差降序排列，若相同则按字典序升序排列，取第一个结果。

三、代码解析

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <climits>
using namespace std;

// 计算字符串相邻字符的最小绝对差
int diff(string& s) {
    int mind = INT_MAX;
    for(int i = 0; i < (int)s.size() - 1; i++)
        mind = min(mind, abs(s[i + 1] - s[i]));
    return mind;
}

// 自定义排序比较函数：先按最小绝对差降序，再按字典序升序
bool cmp(pair<string, int> a, pair<string, int> b) {
    return a.second == b.second ? a.first < b.first : a.second > b.second;
}

int main() {
    string usr, usr2;
    while(cin >> usr) {
        vector<pair<string, int> > vp;

        // 生成前10个排列
        usr2 = usr;
        for(int i = 1; i <= 10; i++) {
            prev_permutation(usr.begin(), usr.end());
            vp.push_back(make_pair(usr, diff(usr)));
        }

        // 添加原用户名
        vp.push_back(make_pair(usr2, diff(usr2)));

        // 生成后10个排列
        for(int i = 1; i <= 10; i++) {
            next_permutation(usr2.begin(), usr2.end());
            vp.push_back(make_pair(usr2, diff(usr2)));
        }

        // 排序并输出最优解
        sort(vp.begin(), vp.end(), cmp);
        printf("%s%d\n", vp[0].first.c_str(), vp[0].second);
    }
    return 0;
}

四、步骤详解

1. 输入处理：

   • 读取用户名，使用两个副本usr和usr2分别生成前10个和后10个排列。

2. 生成排列：

   • 前10个排列：通过prev_permutation函数生成，每次生成后计算最小绝对差并存储。
   • 原用户名：直接计算其最小绝对差并存储。
   • 后10个排列：通过next_permutation函数生成，同样计算并存储。

3. 计算最小绝对差：

   • diff函数遍历字符串，计算相邻字符的绝对差，并返回最小值。

4. 排序选择：

   • 使用自定义比较函数cmp，先按最小绝对差降序排列，若相同则按字典序升序排列。
   • 排序后的第一个元素即为最优解，直接输出。

五、关键点总结

1. 排列生成：

   • 使用标准库函数prev_permutation和next_permutation高效生成排列，确保顺序正确。

2. 排序策略：

   • 自定义比较函数确保按题目要求排序，优先选择最小绝对差大的，再选字典序小的。

3. 复杂度分析：

   • 生成21个排列的时间复杂度为O(21n)，排序复杂度为O(21log21)，整体高效。

4. 边界处理：

   • 题目保证用户名长度不超过20，字符无重复，无需额外处理。

该解法通过直接生成排列、计算特征值、排序选择的三步流程，简洁高效地解决了密码生成问题，确保符合题目约束和要求。