#P2766. 第2题-小红的排列
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 45
            Accepted: 9
            Difficulty: 5
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年3月29日-阿里淘天(开发岗)
                              
                      
          
 
- 
                        算法标签>贪心算法          
 
第2题-小红的排列
题解
算法思路
题目要求给排列中的每个数字前面加上正号或负号,使得整个表达式的值等于给定的 x。注意到排列中的数字均为 1~n,故它们的总和为
S=1+2+⋯+n=2n(n+1)
设正号部分的和为 P,负号部分的和为 N,则有:
- P−N=x
 - P+N=S
 
由此可解得:
- P=2x+S
 - N=2S−x
 
由于实际上只需在某些数字前标记负号,使得负号部分数字的和为 N=2S−x(记作 target),因此问题就转换为:
从集合 {1,2,…,n} 中选择一些数字,其和恰好为 target。
需要注意两个条件:
- 若 S<x 或 (S−x) 为奇数,则无解。
 - 对于集合 {1,2,…,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 ,由整数构成的排列 {a1,a2,...,an} ,她希望你给每个元素前面均标记一个符号:正号′+’或负号′−’,使得所有元素之和等于 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 个两两不同的正整数 a1,a2,...,an(1≦ai≦n)代表小红拿到的排列。
输出描述
如果无解,请输出 −1 。
否则输出一个长度为 n,仅由 ′+′和 ′−′两种符号组成的字符串,第 i 个符号代表所给定的排列中,第 i 个元素前面的符号。
如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
样例1
输入
3 0
1 3 2
输出
-+-
说明
−1+3−2=0,合法。
输出 “+−+” 也是可以的。
样例2
输入
4 11
3 1 4 2
输出
-1