题解 | #动态整数集最近值提取#

题目链接

动态整数集最近值提取

题目描述

你需要维护一个初始为空的整数集合（不允许重复），支持以下两种操作：

1 x：向集合中插入一个整数 x。如果 x 已经存在，则输出 Already Exist。
2 x：从集合中提取一个元素。规则如下：
- 如果集合为空，输出 Empty。
- 否则，在集合中找到与 x 的绝对差最小的元素，将其从集合中删除，并输出该元素的值。
- 如果存在两个这样的元素（即与 x 等距），则选择并删除较小的那个。

输入描述:

第一行一个整数 q（ $1 \le q \le 10^5$ ），表示操作总数。
接下来 q 行，每行输入操作类型 op（1 或 2）和操作数 x。

输出描述:

根据操作要求，在单独一行输出结果。

示例输入:

输出:

15
20

解题思路

本题要求我们维护一个动态的、有序的整数集合，并能高效地找到与给定值 x "最接近"的数。这道题是主函数模式，需要我们自己编写完整的程序。

核心数据结构：平衡二叉搜索树是完成此任务的理想选择，因为它能以对数时间复杂度支持插入、删除和查找。
- C++: std::set
- Java: java.util.TreeSet
- Python: 使用 list + bisect 模块模拟，但删除操作为线性复杂度，可能超时。
操作1：插入 (1 x)
- 在插入前，先用 find/contains 检查 x 是否已在集合中。
- 如果存在，输出 Already Exist。
- 否则，执行插入操作。
操作2：提取 (2 x)
1. 判空：首先检查集合是否为空，若是则输出 Empty。
2. 寻找候选者：与 x 绝对差最小的元素，必然是 x 在集合中的前驱（小于 x 的最大元素）或后继（大于 x 的最小元素）。
  - 我们可以使用 lower_bound (或类似功能) 找到集合中第一个不小于 x 的元素，这个元素就是后继 (candidate 2)。
  - 后继的前一个元素就是前驱 (candidate 1)。
3. 比较与决策：
  - 只有前驱: 选择前驱。
  - 只有后继: 选择后继。
  - 两者都有: 计算 x 到两者的距离 diff1 = x - pred 和 diff2 = succ - x。
    - 若 diff1 <= diff2，选择前驱。（<= 包含了题目中"距离相等时取较小者"的规则）。
    - 否则，选择后继。
4. 执行：确定要提取的元素后，输出它，并从集合中将其删除。

代码

cpp
java
python

#include <iostream>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> q;

    set<int> s;

    while (q--) {
        int op, x;
        cin >> op >> x;

        if (op == 1) {
            if (s.count(x)) {
                cout << "Already Exist\n";
            } else {
                s.insert(x);
            }
        } else { // op == 2
            if (s.empty()) {
                cout << "Empty\n";
                continue;
            }

            auto it_succ = s.lower_bound(x);
            
            int to_remove;

            if (it_succ == s.begin()) { // 只有后继
                to_remove = *it_succ;
            } else if (it_succ == s.end()) { // 只有前驱
                to_remove = *(--it_succ);
            } else { // 前驱和后继都存在
                auto it_pred = prev(it_succ);
                long long diff_pred = (long long)x - *it_pred;
                long long diff_succ = (long long)*it_succ - x;
                
                if (diff_pred <= diff_succ) {
                    to_remove = *it_pred;
                } else {
                    to_remove = *it_succ;
                }
            }
            cout << to_remove << "\n";
            s.erase(to_remove);
        }
    }
    return 0;
}

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        TreeSet<Integer> set = new TreeSet<>();

        for (int i = 0; i < q; i++) {
            int op = scanner.nextInt();
            int x = scanner.nextInt();

            if (op == 1) {
                if (!set.add(x)) {
                    System.out.println("Already Exist");
                }
            } else { // op == 2
                if (set.isEmpty()) {
                    System.out.println("Empty");
                    continue;
                }

                Integer succ = set.ceiling(x); // 后继
                Integer pred = set.floor(x);   // 前驱

                int toRemove;
                if (pred == null) {
                    toRemove = succ;
                } else if (succ == null) {
                    toRemove = pred;
                } else {
                    long diffPred = (long)x - pred;
                    long diffSucc = (long)succ - x;
                    if (diffPred <= diffSucc) {
                        toRemove = pred;
                    } else {
                        toRemove = succ;
                    }
                }
                System.out.println(toRemove);
                set.remove(toRemove);
            }
        }
    }
}

import sys
import bisect

def main():
    q = int(sys.stdin.readline())
    s = []
    
    for _ in range(q):
        op, x = map(int, sys.stdin.readline().split())

        if op == 1:
            idx = bisect.bisect_left(s, x)
            if idx < len(s) and s[idx] == x:
                sys.stdout.write("Already Exist\n")
            else:
                s.insert(idx, x)
        else: # op == 2
            if not s:
                sys.stdout.write("Empty\n")
                continue

            idx_succ = bisect.bisect_left(s, x)
            
            to_remove = 0

            if idx_succ == 0: # 只有后继
                to_remove = s[0]
            elif idx_succ == len(s): # 只有前驱
                to_remove = s[-1]
            else: # 前驱和后继都存在
                pred = s[idx_succ - 1]
                succ = s[idx_succ]
                
                diff_pred = x - pred
                diff_succ = succ - x
                
                if diff_pred <= diff_succ:
                    to_remove = pred
                else:
                    to_remove = succ
            
            sys.stdout.write(str(to_remove) + "\n")
            
            # Python list.remove is O(N), for sorted list it could be faster
            # but bisect.bisect_left + pop is cleaner to implement
            s.pop(bisect.bisect_left(s, to_remove))

if __name__ == "__main__":
    main()

算法及复杂度

算法: 平衡二叉搜索树 (或模拟实现)
时间复杂度:
- C++/Java: 集合所有操作均为 $\mathcal{O}(\log N)$ ，其中 N 是集合中元素个数。总复杂度为 $\mathcal{O}(Q \log N)$ 。
- Python: 查找为 $\mathcal{O}(\log N)$ ，但插入和删除为 $\mathcal{O}(N)$ 。总复杂度最坏为 $\mathcal{O}(Q \cdot N)$ ，可能在极端数据下超时。
空间复杂度: $\mathcal{O}(Q)$ ，最坏情况下所有插入操作都成功，需要存储 Q 个元素。