题解

算法思路

题目要求给排列中的每个数字前面加上正号或负号，使得整个表达式的值等于给定的 x。注意到排列中的数字均为 1~n，故它们的总和为
$S = 1+2+\cdots+n = \frac{n(n+1)}{2}$
设正号部分的和为 P，负号部分的和为 N，则有：

• $P - N = x$
• $P + N = S$

由此可解得：

• $P = \frac{x+S}{2}$
• $N = \frac{S-x}{2}$

由于实际上只需在某些数字前标记负号，使得负号部分数字的和为 $N=\frac{S-x}{2}$（记作 target），因此问题就转换为：
从集合 $\{1,2,\ldots,n\}$ 中选择一些数字，其和恰好为 target。

需要注意两个条件：

1. 若 $S < x$ 或 $(S - x)$ 为奇数，则无解。
2. 对于集合 $\{1,2,\ldots,n\}$，可以采用贪心算法：从最大的数字 $n$ 开始，若当前数字 $i$ 不超过 target，则选择 $i$ 并将 target 减去 $i$。这种方法在该集合中总能得到正确答案。

最终，根据选中的数字（即负号部分）构造答案字符串：若某个数字在集合中，则该位置输出 '-'，否则输出 '+'。

复杂度分析

• 时间复杂度： O(n)
  计算总和、贪心选择以及构造答案均需要遍历数字集合或排列。
• 空间复杂度： O(n)
  主要用于存储选中的数字集合以及答案字符串。

Python 代码

def solve(n, x, a):
    # 计算排列中所有数字的总和
    total = sum(a)
    # 判断是否有解：总和必须不小于 x 且 (total - x) 必须为偶数
    if total < x or (total - x) % 2 != 0:
        return -1
    
    # 计算负号部分数字的目标和
    target = (total - x) // 2
    
    # 使用贪心策略，从大到小选择数字，确保能凑出 target
    chosen = set()
    for i in range(n, 0, -1):
        if target >= i:
            target -= i
            chosen.add(i)
    
    # 如果目标和没有达到 0，则无解
    if target != 0:
        return -1
    
    # 根据选取情况构造答案字符串，遍历输入的排列
    ans = ""
    for num in a:
        if num in chosen:
            ans += "-"
        else:
            ans += "+"
    return ans

# 读入数据
n, x = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
print(solve(n, x, a))

JAVA 代码

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读入 n 和 x
        int n = sc.nextInt();
        int x = sc.nextInt();
        
        int[] a = new int[n];
        long total = 0;
        // 读入排列，并计算总和
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            total += a[i];
        }
        
        // 若总和小于 x 或 (total - x) 不是偶数，则无解
        if (total < x || (total - x) % 2 != 0) {
            System.out.println(-1);
            return;
        }
        
        int target = (int)((total - x) / 2);
        // 使用 HashSet 存储选择负号的数字
        Set<Integer> chosen = new HashSet<>();
        // 贪心选择：从 n 到 1，若数字 i 不超过 target，则选取 i，并更新 target
        for (int i = n; i >= 1; i--) {
            if (target >= i) {
                target -= i;
                chosen.add(i);
            }
        }
        
        // 如果 target 不为 0，则说明无解
        if (target != 0) {
            System.out.println(-1);
            return;
        }
        
        // 根据选择构造答案字符串
        StringBuilder sb = new StringBuilder();
        for (int num : a) {
            if (chosen.contains(num)) {
                sb.append("-");
            } else {
                sb.append("+");
            }
        }
        System.out.println(sb.toString());
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    long long total = 0;
    // 读入排列，并计算总和
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }
    
    // 若总和小于 x 或 (total - x) 不是偶数，则无解
    if (total < x || (total - x) % 2 != 0) {
        cout << -1 << "\n";
        return 0;
    }
    
    int target = (total - x) / 2;
    unordered_set<int> chosen;
    // 贪心选择：从 n 到 1，若当前数字 i 不超过 target，则选取该数字并更新 target
    for (int i = n; i >= 1; i--) {
        if (target >= i) {
            target -= i;
            chosen.insert(i);
        }
    }
    
    // 如果 target 不为 0，则无解
    if (target != 0) {
        cout << -1 << "\n";
        return 0;
    }
    
    // 根据选择结果输出对应符号，保持与输入排列顺序一致
    for (int num : a) {
        if (chosen.count(num)) {
            cout << "-";
        } else {
            cout << "+";
        }
    }
    cout << "\n";
    
    return 0;
}

题目内容

小红拿到了一个长度为 $n$ ，由整数构成的排列 {$a_1,a_2,...,a_n$} ，她希望你给每个元素前面均标记一个符号：正号$'+’$或负号$'-’$，使得所有元素之和等于 $x$ 。你能帮帮她吗?

长度为 $n$ 的排列是由 $1$~ $n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而{$1,2,2$}和{$1,3,4$}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。每个元素恰好出现 $1$ 次。

输入描述

第一行输入两个正整数 n,x(1 ≤ n ≤ 10^5;0 ≦x≦ 10^9)代表排列的长度、要求的和。

第二行输入 $n$ 个两两不同的正整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ n)$代表小红拿到的排列。

输出描述

如果无解，请输出 $-1$ 。

否则输出一个长度为 $n$，仅由 $'+'$和 $'-'$两种符号组成的字符串，第 $i$ 个符号代表所给定的排列中，第 $i$ 个元素前面的符号。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3 0
1 3 2

输出

-+-

说明

$-1+3-2=0$，合法。

输出 $“+-+”$ 也是可以的。

样例2

输入

4 11
3 1 4 2

输出

-1