题解

题意分析

题目描述了一个加油站油价显示的问题：

• 油价由数字和一个小数点组成（小数点固定位于倒数第二位）
• 某些数字可以倒置使用（如$6$和$9$互换，$2$和$5$互换）
• 需要找到使用相同数字（可倒置）能组成的下一个更高油价
• 输入保证格式正确（无前导零，除非价格小于$1$）
• 输出下一个更高油价或"无法提高油价"

解题思路

1. 数字转换规则：确定每个数字可能的替代形式（如$2$可变为$5$）
2. 生成所有可能组合：使用回溯法生成所有可能的数字排列组合
3. 验证有效性：检查生成的数字是否符合油价格式要求
4. 寻找最小更大值：在所有有效组合中找出比原价格大的最小值

实现步骤

1. 输入处理：逐行读取油价直到遇到单独的小数点
2. 生成可能数字：
   • 为每个数字位置确定可能的替代数字
   • 使用回溯法生成所有排列组合
3. 验证价格格式：
   • 检查长度和小数点位置
   • 验证无非法前导零
4. 寻找解：
   • 过滤有效价格
   • 找出比原价格大的最小值
5. 输出结果

代码注释

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
#include <set>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

// 生成所有可能的数字组合（考虑数字倒置）
vector<string> generate_possible_numbers(const string &original) {
    vector<vector<char>> possible_digits; // 存储每个位置可能的数字
    
    // 确定每个数字可能的替代形式
    for (char c : original) {
        vector<char> replacements;
        switch (c) {
            case '0': replacements = {'0'}; break; // 0不能倒置
            case '1': replacements = {'1'}; break; // 1不能倒置
            case '2': replacements = {'2', '5'}; break; // 2可变为5
            case '5': replacements = {'5', '2'}; break; // 5可变为2
            case '6': replacements = {'6', '9'}; break; // 6可变为9
            case '8': replacements = {'8'}; break; // 8不能倒置
            case '9': replacements = {'9', '6'}; break; // 9可变为6
            case '.': replacements = {'.'}; break; // 小数点不变
            default: replacements = {c}; break; // 其他字符不变
        }
        possible_digits.push_back(replacements);
    }
    
    // 使用回溯法生成所有组合
    vector<string> numbers;
    function<void(int, string)> backtrack = [&](int pos, string current) {
        if (pos == possible_digits.size()) { // 到达字符串末尾
            numbers.push_back(current);
            return;
        }
        for (char c : possible_digits[pos]) { // 尝试当前位置所有可能数字
            backtrack(pos + 1, current + c);
        }
    };
    backtrack(0, ""); // 从位置0开始回溯
    return numbers;
}

// 验证生成的数字是否符合油价格式
bool is_valid_price(const string &s, const string &original) {
    // 长度必须相同
    if (s.length() != original.length()) return false;
    
    // 小数点位置必须相同
    int dot_pos_original = original.find('.');
    int dot_pos_s = s.find('.');
    if (dot_pos_original != dot_pos_s) return false;
    
    // 小数点必须在倒数第二位
    if (dot_pos_s != s.length() - 2) return false;
    
    // 检查前导零：只有当小数点在第2位时才允许首位为0
    if (s[0] == '0' && dot_pos_s != 1) {
        return false;
    }
    return true;
}

// 主求解函数
string solve(const string &original) {
    // 生成所有可能的数字组合
    vector<string> possible_numbers = generate_possible_numbers(original);
    set<string> valid_numbers; // 使用set自动排序和去重
    
    // 筛选有效的价格格式
    for (const string &num : possible_numbers) {
        if (is_valid_price(num, original)) {
            valid_numbers.insert(num);
        }
    }
    
    // 找出比原价格大的最小值
    double original_value = stod(original);
    double min_greater = -1;
    string result;
    for (const string &num : valid_numbers) {
        double value = stod(num);
        if (value > original_value) {
            if (min_greater == -1 || value < min_greater) {
                min_greater = value;
                result = num;
            }
        }
    }
    
    // 返回结果
    if (min_greater == -1) {
        return "The price cannot be raised.";
    } else {
        return result;
    }
}

int main() {
    string line;
    while (getline(cin, line)) { // 读取输入直到遇到单独的小数点
        if (line == ".") break;
        cout << solve(line) << endl; // 处理并输出结果
    }
    return 0;
}

复杂度分析

• 时间复杂度：最坏情况下为$O(2^n)$，其中$n$为数字位数（每个数字最多有$2$种可能）
• 空间复杂度：$O(2^n)$，需要存储所有可能的组合