#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define PII pair<int, int>
#define PDI pair<double, int>
#define all(x) x.begin(), x.end()
#define quickcin() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e4 + 10, MINRAND = 0, MAXRAND = 1e9;

mt19937 rnd1(time(0));
mt19937_64 rnd2(time(0));
uniform_int_distribution<> int_mt(MINRAND, MAXRAND);
uniform_real_distribution<> double_mt(MINRAND, MAXRAND);
int n, k, minn, maxn;
int a[N], used[N];
vector<int> res;
void dfs(int l, int r)
{
    if (l == r)
    {
        if (!used[l])
            res.pb(a[l]);
        return;
    }
    int mid = l + r >> 1;
    int x = a[mid];
    if (mid - 1 >= l)
        used[mid] = 1, dfs(l, mid - 1);
    if (mid + 1 <= r)
        used[mid] = 1, dfs(mid + 1, r);
    return;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> k >> minn >> maxn;
    sort(a + 1, a + n + 1, less<int>());
    dfs(1, n);
    sort(all(res), greater<int>());
    int ans = 0, choice = 0;
    for (auto i : res)
    {
        if (i > maxn)
            continue;
        if (i >= minn && i <= maxn && choice <= k)
        {
            choice++;
            ans += i;
        }
        else
            break;
    }
    // cout << k << " " << choice << endl;
    if (choice == k)
        cout << ans;
    else if (choice == 0)
        cout << res[0];
    else
        cout << -1;
}

signed main()
{
    quickcin();
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}

思路:递归建树 + 模拟

1. 构建平衡二叉搜索树： 1.根据题意，将输入的节点值进行升序排序。 2.使用递归的方法，选择中间元素作为当前根节点，递归构建左右子树，保证平衡。

2. 收集叶子节点： 遍历整棵树，找到所有叶子节点（左右子树均为空的节点），并将它们的值存入列表。

3. 处理查询条件：

   • 从收集到的叶子节点中，筛选出符合 min_val <= val <= max_val 的节点值。
   • 如果找到的叶子节点数量与查询的数量 q 相等，则返回这些节点的值之和。
   • 如果没有符合条件的叶子节点，则返回叶子节点中的最大值。
   • 如果符合条件的节点数量不等于 q 且不为空，则返回 -1。

代码

python

# 定义二叉树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 从排序好的列表构建平衡二叉搜索树
def build_balanced_bst(sorted_list, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    node = Node(sorted_list[mid])
    node.left = build_balanced_bst(sorted_list, start, mid - 1)
    node.right = build_balanced_bst(sorted_list, mid + 1, end)
    return node

# 收集平衡二叉树的叶子节点值
def collect_leaf_nodes(root, leaf_nodes):
    if root is None:
        return
    if root.left is None and root.right is None:
        leaf_nodes.append(root.val)
    else:
        collect_leaf_nodes(root.left, leaf_nodes)
        collect_leaf_nodes(root.right, leaf_nodes)

def main():
    # 读取第一行输入
    parts = list(map(int, input().split()))
    n = parts[0]  # 节点数量
    node_values = parts[1:]
    
    # 对节点值进行排序
    sorted_values = sorted(node_values)
    
    # 构建平衡二叉搜索树
    root = build_balanced_bst(sorted_values, 0, n - 1)
    
    # 收集所有叶子节点的值
    leaf_nodes = []
    collect_leaf_nodes(root, leaf_nodes)
    
    if not leaf_nodes:
        print(-1)
        return
    
    max_leaf = max(leaf_nodes)  # 叶子节点的最大值
    
    # 读取第二行输入
    query_parts = list(map(int, input().split()))
    
    q, min_val, max_val = query_parts[:3]  # 查询参数：期望数量，最小值，最大值
    
    # 找出满足查询范围的叶子节点
    valid_leaves = [val for val in leaf_nodes if min_val <= val <= max_val]
    
    if len(valid_leaves) == q:
        print(sum(valid_leaves))
    elif len(valid_leaves) == 0:
        print(max_leaf)
    else:
        print(-1)

if __name__ == "__main__":
    main()

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

C++

#include <bits/stdc++.h>
using namespace std;

int sumleaf = 0;  // 存储符合条件的叶子节点值的总和
int maxleaf = 0;  // 存储所有叶子节点中的最大值
int count1 = 0;   // 记录符合条件的叶子节点的数量

// 二叉树节点定义
struct TreeNode
{
    int val;  // 节点的值
    TreeNode *left;  // 左子节点
    TreeNode *right; // 右子节点

    // 构造函数，初始化节点值，并设置左右子节点为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 使用有序数组构建平衡二叉树
TreeNode *buildTree(vector<int> &inputs, int l, int r)
{
    // 当左索引大于右索引时，返回空，表示没有更多节点
    if (l > r)
        return nullptr;
    
    // 取中间元素作为当前节点，确保树的平衡
    int mid = (r + l) / 2;
    
    // 创建一个新节点，并递归构建其左子树和右子树
    TreeNode *root = new TreeNode(inputs[mid]);
    root->left = buildTree(inputs, l, mid - 1);  // 递归构建左子树
    root->right = buildTree(inputs, mid + 1, r); // 递归构建右子树
    
    return root;  // 返回根节点
}

// 寻找叶子节点并计算符合条件的叶子节点总和
void findLeaf(TreeNode *root, int minv, int maxv)
{
    if (root == nullptr)
        return;  // 当前节点为空，直接返回

    // 如果当前节点是叶子节点（没有左子树和右子树）
    if (root->left == nullptr && root->right == nullptr)
    {
        // 判断叶子节点的值是否在给定的范围内
        if (root->val >= minv && root->val <= maxv)
        {
            sumleaf += root->val;  // 累加符合条件的叶子节点的值
            count1++;  // 记录符合条件的叶子节点的数量
        }
    }

    // 更新所有叶子节点中的最大值
    maxleaf = max(maxleaf, root->val);
    
    // 递归搜索左子树和右子树
    findLeaf(root->left, minv, maxv);
    findLeaf(root->right, minv, maxv);
}

int main()
{
    int n;
    cin >> n;  // 输入节点的数量

    // 输入数组，存储二叉树的节点值
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];  // 逐个输入节点的值
    }

    // 输入查询范围和期望匹配的叶子节点数量
    int m, minv, maxv;
    cin >> m >> minv >> maxv;
    
    // 对数组进行排序，确保能够构建平衡二叉树
    sort(a.begin(), a.end());

    // 构建平衡二叉树
    TreeNode *root = buildTree(a, 0, n - 1);
    
    // 查找符合条件的叶子节点
    findLeaf(root, minv, maxv);
    
    // 根据符合条件的叶子节点的数量与期望的数量 `m` 进行判断
    if (m == count1)
    {
        // 如果符合条件的叶子节点数量等于 `m`，输出这些节点值的总和
        cout << sumleaf << endl;
    }
    else if (count1 == 0)
    {
        // 如果没有符合条件的叶子节点，输出所有叶子节点中的最大值
        cout << maxleaf << endl;
    }
    else
    {
        // 如果符合条件的叶子节点数量不等于 `m`，输出 -1
        cout << -1 << endl;
    }

    return 0;  // 返回程序成功运行的状态
}

java

import java.util.*;

// 二叉树节点定义
class TreeNode {
    int val;  // 节点的值
    TreeNode left;  // 左子节点
    TreeNode right; // 右子节点

    // 构造函数，初始化节点值，并设置左右子节点为空
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class Main {
    static int sumleaf = 0;  // 存储符合条件的叶子节点值的总和
    static int maxleaf = 0;  // 存储所有叶子节点中的最大值
    static int count1 = 0;   // 记录符合条件的叶子节点的数量

    // 使用有序数组构建平衡二叉树
    public static TreeNode buildTree(List<Integer> inputs, int l, int r) {
        if (l > r) {
            return null;  // 当左索引大于右索引时，返回空
        }

        int mid = (r + l) / 2;  // 取中间元素作为当前节点
        TreeNode root = new TreeNode(inputs.get(mid));  // 创建新节点
        root.left = buildTree(inputs, l, mid - 1);  // 递归构建左子树
        root.right = buildTree(inputs, mid + 1, r); // 递归构建右子树
        return root;  // 返回根节点
    }

    // 寻找叶子节点并计算符合条件的叶子节点总和
    public static void findLeaf(TreeNode root, int minv, int maxv) {
        if (root == null) {
            return;  // 当前节点为空，直接返回
        }

        // 如果当前节点是叶子节点（没有左子树和右子树）
        if (root.left == null && root.right == null) {
            if (root.val >= minv && root.val <= maxv) {
                sumleaf += root.val;  // 累加符合条件的叶子节点的值
                count1++;  // 记录符合条件的叶子节点的数量
            }
        }

        maxleaf = Math.max(maxleaf, root.val);  // 更新所有叶子节点中的最大值
        findLeaf(root.left, minv, maxv);  // 递归搜索左子树
        findLeaf(root.right, minv, maxv); // 递归搜索右子树
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();  // 输入节点的数量
        List<Integer> a = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            a.add(scanner.nextInt());  // 逐个输入节点的值
        }

        int m = scanner.nextInt();  // 输入期望的叶子节点数量
        int minv = scanner.nextInt();  // 输入最小值范围
        int maxv = scanner.nextInt();  // 输入最大值范围

        Collections.sort(a);  // 对数组进行排序

        TreeNode root = buildTree(a, 0, n - 1);  // 构建平衡二叉树
        findLeaf(root, minv, maxv);  // 查找符合条件的叶子节点

        if (m == count1) {
            System.out.println(sumleaf);  // 输出符合条件叶子节点的总和
        } else if (count1 == 0) {
            System.out.println(maxleaf);  // 如果没有符合条件的叶子节点，输出最大值
        } else {
            System.out.println(-1);  // 如果符合条件叶子节点数量不等于 `m`，输出 -1
        }

        scanner.close();
    }
}