题目内容

小红拿到了一个长度为 $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$ 次。

输入描述

题解

算法思路

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

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