【CSP-J 模拟赛二】E 题 智慧（wisdom.cpp）题解

题目描述

给定三个整数 a、b、c 和目标值 target，判断是否可以通过调整这三个数的顺序，并仅使用加号或减号连接它们，使得计算结果等于 target。如果可以，输出 YES，否则输出 NO。

输入格式
四个整数 a、b、c、target。

输出格式
YES 或 NO。

样例
输入：5 7 2 4
输出：YES
（解释：5 + 7 - 2 = 10，但通过调整顺序为 7 - 5 + 2 = 4）

传送门

思路分析

核心思路

1. 全排列生成：由于三个数的顺序可以调换，首先生成所有可能的排列组合。
2. 符号组合遍历：对于每一种排列，尝试所有可能的加减符号组合（共 2^2 = 4 种）。
3. 结果验证：计算每种排列和符号组合的结果，若等于 target，则返回 YES。

关键步骤

1. 全排列：使用 next_permutation 生成所有可能的排列。
2. 符号枚举：通过位运算枚举两个运算符的符号（+ 或 -）。
3. 快速判断：一旦找到符合条件的组合，立即返回结果，避免冗余计算。

代码实现

cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c, target;
    cin >> a >> b >> c >> target;
    int nums[3] = {a, b, c};
    sort(nums, nums + 3); // 排序以便生成全排列

    do {
        // 枚举两个运算符的符号组合（共4种可能）
        for (int i = 0; i < 4; i++) {
            int sign1 = (i & 2) ? -1 : 1; // 第二位控制第一个运算符
            int sign2 = (i & 1) ? -1 : 1; // 第一位控制第二个运算符
            int result = nums[0] + sign1 * nums[1] + sign2 * nums[2];
            if (result == target) {
                cout << "YES" << endl;
                return 0;
            }
        }
    } while (next_permutation(nums, nums + 3)); // 生成下一个排列

    cout << "NO" << endl;
    return 0;
}

代码解释

1. 输入处理
   读取四个整数 a、b、c 和 target，并将 a、b、c 存入数组 nums。
2. 全排列生成
   • 使用 sort 对数组排序，确保 next_permutation 能生成所有排列。
   • do-while 循环结合 next_permutation 遍历所有排列。
3. 符号组合枚举
   • 通过位掩码 i 的两位分别控制两个运算符的符号：
     • i & 2（二进制第二位）决定第一个运算符是否为减号。
     • i & 1（二进制第一位）决定第二个运算符是否为减号。
   • 计算表达式 nums[0] ± nums[1] ± nums[2] 的结果。
4. 结果验证
   若某次计算结果等于 target，立即输出 YES 并结束程序。遍历完所有可能后仍未找到匹配项，输出 NO。

复杂度分析

• 时间复杂度：
  全排列共有 3! = 6 种，每种排列对应 4 种符号组合，总共有 6 × 4 = 24 种情况。每种情况的计算为常数时间，因此总时间复杂度为 O(1)。
• 空间复杂度：
  仅使用固定大小的数组和变量，空间复杂度为 O(1)。

关键点总结

1. 全排列的巧妙运用：通过 next_permutation 生成所有可能的顺序组合。
2. 位运算优化符号枚举：利用二进制位掩码快速生成所有符号组合。
3. 提前终止：一旦找到符合条件的组合，立即返回结果，避免不必要的计算。

其他题解