OJ: HDU

题目 ID: 5233

标签:

日期: 2026-01-02 18:13

题目解析

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-02 21:28:11
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int h[maxn];
// 桶:buckets[i] 存储的是 离散化后排名为 i 的所有树的原始下标
vector<int> buckets[maxn];
// 头指针:head[i] 表示 buckets[i] 当前处理到了第几个元素
// 代替 pop_front,实现 O(1) 的伪删除
int head[maxn];

//oisnip_begindiscrete离散化_unique.cpp
/**  
* 步骤1:加入数据
*   for (int x : nums) d.add(x);
* 步骤2:构建
*   d.build();
* 步骤3:使用
*   去重后大小: :  d.size() 
*   for (int x : nums) cout << x << " -> " << d.get(x) << endl;
*/
struct Discrete {
    std::vector<int> xs;

    inline void clear() { xs.clear(); }

    // 1. 添加元素
    void add(int x) { xs.push_back(x); }

    // 2. 构建:排序并去重
    void build() {
        std::sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
    }

    // 3. 查询 x 映射后的值 (默认从 1 开始)
    // 如果找不到,返回的数值可能会超出范围,具体视 lower_bound 行为而定
    int get(int x) {
        return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
    }

    //  可能得找不到对应的值
    int get_maybe(int x) {
        // 直接使用 lower_bound 查找迭代器
        auto it = std::lower_bound(xs.begin(), xs.end(), x);
        
        // 1. 检查是否到达末尾 (所有数都比 x 小)
        // 2. 检查找到的值是否严格等于 x (lower_bound 只是找 >= 的)
        if (it == xs.end() || *it != x) {
            return -1;
        }
        
        // 转换为 1-based 下标返回
        return it - xs.begin() + 1;
    }

    // 3.2 查询 x 映射后的最大的值 (从 1 开始)
    int get_max() {
        return xs.size();
    }
    
    // 3.1 查询 x 映射后的值 (从 0 开始)
    int get_zero(int x) {
        return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    }

    // 4. 反向查询:根据离散化后的值 k 找回 原值 (k 从 1 开始)
    int origin(int k) {
        return xs[k - 1];
    }
    
    // 获取去重后的元素总数
    int size() {
        return xs.size();
    }
} disc;
//oisnip_end

void init(){
    disc.clear();
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        buckets[i].clear();
        head[i] = 0;
    }
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> h[i];
        disc.add(h[i]);
    }
    disc.build();
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    while ( std::cin >> n >> m ) {
        init();

        // -> 将树的下标放入对应的桶中
        // 注意:这里我们正序遍历 (1 -> n),放入桶中也是有序的 (小 -> 大)
        // 配合 head 指针从 0 开始自增,天然满足“取最左边”的要求
        for (int i = 1; i <= n; ++i) {
            // 因为 h[i] 一定在 uniq_h 里,这里直接二分找下标
            int id = disc.get(h[i]);
            buckets[id].push_back(i); // 放入高度为h[i[ 对应的下标
        }

        // 处理询问
        for(int i = 1;i <= m ;++i ) // i: 1->m
        {
            int q;
            std::cin >> q;
            int id = disc.get_maybe(q);
            // 情况1: 这个高度根本没出现过
            if( id == -1) {
                std::cout << -1 << "\n";
                continue;
            }

            // 情况2: 这个高度出现过,但是桶里的鸟都被打完了
            // head[id] 已经指到了 vector 的末尾
            if( head[id] >= buckets[id].size())
            {
                std::cout << -1 << "\n";
                continue;
            }

            // 情况3: 击中!
            std::cout << buckets[id][head[id]] << "\n";
            // 指针后移,相当于“删除”了这只鸟
            head[id]++;

        }
    }
    
    return 0;
}