QOJ.ac

QOJ

시간 제한: 3 s 메모리 제한: 1024 MB 총점: 100

#15188. 堆结构

통계

最小二叉堆(通常简称为“小根堆”)是计算机科学中一种基于二叉树的特殊数据结构。它是一棵具有以下两个主要性质的二叉树:

  1. 堆性质:在小根堆中,对于任意给定的节点,该节点的值小于或等于其子节点的值。这意味着堆中的最小值总是位于根节点。换句话说,堆中最小的元素在最顶部。
  2. 二叉树结构:小根堆通常是一棵完全二叉树,这意味着除了最后一层外,树的所有层都被完全填满,而最后一层则是从左到右填充的。这种结构特性使得小根堆可以高效地使用数组来实现。

小根堆常用于实现优先队列,优先队列是一种维护具有关联优先级的元素集合的数据结构。通过将最小元素保持在根节点,小根堆可以在对数时间内快速检索并删除具有最高优先级(最小值)的元素。然而,从小根堆中删除任何其他元素可能需要线性时间。

Hank 最近学习了小根堆。他想知道,在一个包含 $n$ 个节点的小根堆中,有多少个节点可以存放第 $k$ 小的元素。请编写一个程序来帮助他。

输入格式

输入包含两个空格分隔的正整数 $n$ 和 $k$。

输出格式

输出在一个包含 $n$ 个节点的小根堆中,可以存放第 $k$ 小的元素的节点数量。

数据范围

$1 \le k \le n \le 10^{18}$

样例

输入样例 1

100 1

输出样例 1

1

输入样例 2

12 3

输出样例 2

6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.