N. Fixing the Expression - 题解

比赛与标签

比赛: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) 标签: implementation 难度: *800

题目大意喵~

主人你好呀！这道题目是关于一个叫做“表达式”的特殊字符串的说。

这个表达式由三个字符组成：一个数字，一个比较符号（<, =, >），再加一个数字。比如 3<7 或者 8=8 这样子。

一个表达式如果说的是真话，那它就是“真”的。比如说，1<3 是真的，因为 1 确实小于 3。但 5>5 就不是真的，因为 5 并不大于 5 呐。

我们的任务是，拿到一个表达式字符串 s，用最少最少的改动，让它变成一个“真”的表达式。如果它本来就是真的，那我们什么都不用做，直接把它交上去就好啦！

输入: 会先给我们一个整数 t，表示有 t 组测试数据。 接下来 t 行，每一行都是一个长度为 3 的表达式字符串。

输出: 对于每个表达式，我们要输出一个改动次数最少的“真”表达式。如果有好几种改法，随便输出哪一种都可以哦！

解题思路分析的说

喵哈哈~ 这道题看起来就是要我们分类讨论，然后找出最简单的修复方法！我们的目标是“改动次数最少”，所以要按照改动次数从小到大来考虑呐。

第一步：0 次改动，完美！

最理想的情况当然是表达式本来就是对的啦！我们什么都不用干，这是 0 次改动，是最优解！ 所以，我们首先要检查一下给定的表达式 d1 op d2 是不是真的：

• 如果 op 是 <，我们检查 d1 是不是真的小于 d2。
• 如果 op 是 =，我们检查 d1 是不是真的等于 d2。
• 如果 op 是 >，我们检查 d1 是不是真的大于 d2。

如果满足以上任何一个条件，直接输出原来的字符串 s 就好啦！任务完成，可以去晒太阳了喵~

第二步：1 次改动，修复它！

如果表达式是错的，那我们就至少要改动一个字符。1 次改动是次优的选择，我们来看看怎么只改一个字符就让它变真。

这里有两种思路：要么改运算符，要么改数字。

让我们来分析一下代码里的逻辑，它非常聪明地处理了所有情况，喵~

情况一：如果原来的运算符是 = 比如 8=9。这个表达式是错的，说明 d1 不等于 d2。我们只需要把 = 换成正确的运算符就可以啦！

• 如果 d1 < d2 (比如 8=9 中，8 < 9)，那我们就把它改成 8<9。
• 如果 d1 > d2 (比如 5=2 中，5 > 2)，那我们就把它改成 5>2。 这样只需要改动中间的运算符，花费 1 次改动，问题解决！

情况二：如果原来的运算符是 < 或 > 比如 5<3，这个表达式是错的，因为 5 >= 3。代码的策略是：

1. 优先尝试改动数字：

   • 尝试改左边的数字 d1：对于 5<3，我们想找一个新数字 d1'，让 d1' < 3 成立。我们可以从 0 开始试，0<3 是成立的！太棒了，找到一个解 0<3，只需要改动 1 个字符。
   • 如果改左边不行，就尝试改右边的数字 d2：比如 9<0，我们找不到任何一个数字 d1' 满足 d1' < 0。这时我们就得试试改 d2。我们想找一个新数字 d2'，让 9 < d2' 成立。可惜，数字最大只到 9，所以也找不到这样的 d2'。

2. 没办法了，只能改运算符：

   • 如果上面两种改数字的方法都失败了（比如 9<0 这个例子），那就说明我们必须改运算符了！
   • 对于 9<0，我们知道 9 > 0 是成立的，所以把 < 改成 >，得到 9>0。这也是 1 次改动！
   • 对于 5<3，我们知道 5 > 3 是成立的，所以也可以改成 5>3。

代码的逻辑就是这样，对于 < 和 > 的情况，它会先遍历 0-9 尝试替换第一个数字，如果找到了就输出。如果没找到，再遍历 0-9 尝试替换第二个数字。如果还找不到，最后才会选择修改运算符。

因为题目说任何一个改动次数最少的答案都行，所以这种策略是完全正确的！它总能帮我们找到一个只需要 1 次改动的答案。

总结一下，我们的策略就是：

1. 检查 0 次改动行不行。
2. 如果不行，就找一个 1 次改动的方案。代码里的实现方式是一个非常稳妥的分类讨论，保证能找到解！

代码实现呐

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t; // 读取测试用例的数量
    while (t--) {
        string s;
        cin >> s; // 读取长度为3的表达式字符串
        
        // 把字符拆开方便处理
        char a = s[0];
        char op = s[1];
        char b = s[2];
        
        // 把数字字符转换成整数
        int d1 = a - '0';
        int d2 = b - '0';
        
        // 【0次改动检查】检查表达式是否已经为真
        if ((op == '<' && d1 < d2) || 
            (op == '=' && d1 == d2) || 
            (op == '>' && d1 > d2)) {
            // 如果是真的，直接输出原字符串，不需要改动
            cout << s << '\n';
        } else {
            // 【1次改动修复】如果表达式是假的，我们需要进行修复
            
            // 情况1：原运算符是 '='
            if (op == '=') {
                // 既然 'd1=d2' 是假的，那 d1 肯定不等于 d2
                // 我们只需要把 '=' 改成 '<' 或 '>' 即可
                if (d1 < d2) {
                    cout << a << '<' << b << '\n';
                } else { // d1 > d2
                    cout << a << '>' << b << '\n';
                }
            } 
            // 情况2：原运算符是 '<'
            else if (op == '<') { 
                // 既然 'd1<d2' 是假的，那说明 d1 >= d2
                bool found = false;
                // 优先尝试修改第一个数字 d1
                for (int d = 0; d <= 9; d++) {
                    if (d == d1) continue; // 不改等于没改
                    if (d < d2) {
                        cout << char('0' + d) << op << b << '\n';
                        found = true;
                        break;
                    }
                }
                if (found) continue; // 找到了就处理下一个测试用例
                
                // 如果修改 d1 失败，尝试修改第二个数字 d2
                for (int d = 0; d <= 9; d++) {
                    if (d == d2) continue;
                    if (d1 < d) {
                        cout << a << op << char('0' + d) << '\n';
                        found = true;
                        break;
                    }
                }
                if (found) continue;
                
                // 如果修改数字都失败了（例如 9<0），只能修改运算符
                if (d1 == d2) {
                    cout << a << '=' << b << '\n';
                } else { // d1 > d2
                    cout << a << '>' << b << '\n';
                }
            } 
            // 情况3：原运算符是 '>'
            else if (op == '>') {
                // 既然 'd1>d2' 是假的，那说明 d1 <= d2
                bool found = false;
                // 优先尝试修改第一个数字 d1
                for (int d = 0; d <= 9; d++) {
                    if (d == d1) continue;
                    if (d > d2) {
                        cout << char('0' + d) << op << b << '\n';
                        found = true;
                        break;
                    }
                }
                if (found) continue;
                
                // 如果修改 d1 失败，尝试修改第二个数字 d2
                for (int d = 0; d <= 9; d++) {
                    if (d == d2) continue;
                    if (d1 > d) {
                        cout << a << op << char('0' + d) << '\n';
                        found = true;
                        break;
                    }
                }
                if (found) continue;
                
                // 如果修改数字都失败了，只能修改运算符
                if (d1 == d2) {
                    cout << a << '=' << b << '\n';
                } else { // d1 < d2
                    cout << a << '<' << b << '\n';
                }
            }
        }
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(T) 的说。 对于每一个测试用例，我们的操作都是常数级别的。虽然代码里有 for 循环，但它们最多只会循环 10 次（从 0到9）来寻找一个合适的数字。一旦找到，就会立刻 break。所以处理每个表达式的时间是恒定的。总的时间就是测试用例数量 T 乘以一个常数，也就是 O(T) 啦！
• 空间复杂度: O(1) 的说。 我们在每个测试用例中只用了几个变量来存储字符串和数字，比如 s, a, op, b, d1, d2 等。需要的内存空间不会随着输入规模的改变而改变，是恒定的。所以空间复杂度是 O(1) 呐。

知识点与总结喵！

这道题是一道很棒的 实现(implementation) 和 分类讨论(case analysis) 练习题！它考验的是我们把问题想清楚，然后用代码清晰地表达出来的能力。

1. 最小改动原则: 解决这类问题时，要始终记得“最小改动”这个核心要求。从改动 0 次开始考虑，再考虑改动 1 次，以此类推。这道题因为改动 1 次总能解决问题，所以我们不需要考虑更复杂的情况。
2. 构造性解法: 我们不是在验证什么，而是在“构造”一个符合要求的答案。当发现当前状态不满足条件时，要想办法通过修改来构造一个满足条件的。
3. 代码实现策略: 面对多种可能的修复方案（改数字 vs 改符号），选择一种固定的、能覆盖所有情况的策略很重要。这道题的AC代码选择的策略是“优先改数字，不行再改符号”，这是一种完全可行的策略。其实，更简单的“直接改符号”策略也是可以通过的哦！
4. 边界情况: 要小心那些看起来很极端的例子，比如 9<0 或者 0>9。在这些情况下，修改单个数字可能无法满足条件，这时就需要有备用方案（比如修改运算符）。

总之，只要思路清晰，把所有情况都考虑到，这道题就是一只温顺的小猫咪，很容易就能抓住它的尾巴的！继续加油，主人，你在算法的世界里是最棒的，喵~！