Codeium

01Eric's Sequence

Eric has a sequence of non-negative integers p[0], p[1], ..., p[n-1], and he would like to find a sequence a[0], a[1], ..., a[n-1] of n distinct integers such that

No two (not necessarily distinct) elements a[i] and a[j] sum to 0, and
p[i] is equal to the number of indices j such that a[i] + a[j] > 0 for each 0 If multiple such sequences exist, Eric wants one such that the maximum of the absolute values of the elements a[0], a[1], ..., a[n-1]` is as small as possible. Help Eric, find such a sequence, if possible. Input:
n: A positive integer, the length of Eric's sequence.
p: A list of n non-negative integers representing Eric's sequence. Output: a: A list of n integers satisfying the restrictions given by Eric, including making sure the maximum of the absolute values of a[0], a[1], ..., a[n-1] is as small as possible. If there are still multiple such sequences, return any such sequence. If no such sequence exists, return None.

Constraints

解法

构造法：要让 a[i] 的绝对值最小，最自然的取值是 ±1, ±2, ..., ±n/2 这样的对称集合。按 p[i] 排序后，p 值越大的位置分配越大的正数，越小的分配越小的负数；最后验证构造的序列对每个 i 的 a[i]+a[j]>0 的计数是否真的等于 p[i]，不匹配则返回 None。时间 O(n log n)，空间 O(n)。

from typing import List, Optional

def solve(n: int, p: List[int]) -> Optional[List[int]]:
    order = sorted(range(n), key=lambda i: p[i])
    pool: List[int] = []
    half = (n + 1) // 2
    for k in range(1, half + 1):
        pool.append(-k)
    for k in range(half, 0, -1):
        if len(pool) < n:
            pool.append(k)
    pool.sort()
    a = [0] * n
    for rank, idx in enumerate(order):
        a[idx] = pool[rank]
    for i in range(n):
        cnt = sum(1 for j in range(n) if a[i] + a[j] > 0)
        if cnt != p[i]:
            return None
    return a

import java.util.*;

class Solution {
    int[] solve(int n, int[] p) {
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (x, y) -> p[x] - p[y]);
        List<Integer> pool = new ArrayList<>();
        int half = (n + 1) / 2;
        for (int k = 1; k <= half; k++) pool.add(-k);
        for (int k = half; k >= 1 && pool.size() < n; k--) pool.add(k);
        Collections.sort(pool);
        int[] a = new int[n];
        for (int rank = 0; rank < n; rank++) a[order[rank]] = pool.get(rank);
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) if (a[i] + a[j] > 0) cnt++;
            if (cnt != p[i]) return null;
        }
        return a;
    }
}

#include <vector>
#include <algorithm>
#include <optional>

class Solution {
public:
    std::optional<std::vector<int>> solve(int n, std::vector<int>& p) {
        std::vector<int> order(n);
        for (int i = 0; i < n; i++) order[i] = i;
        std::sort(order.begin(), order.end(), [&](int x, int y) { return p[x] < p[y]; });
        std::vector<int> pool;
        int half = (n + 1) / 2;
        for (int k = 1; k <= half; k++) pool.push_back(-k);
        for (int k = half; k >= 1 && (int)pool.size() < n; k--) pool.push_back(k);
        std::sort(pool.begin(), pool.end());
        std::vector<int> a(n);
        for (int rank = 0; rank < n; rank++) a[order[rank]] = pool[rank];
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) if (a[i] + a[j] > 0) cnt++;
            if (cnt != p[i]) return std::nullopt;
        }
        return a;
    }
};