题解：P10392 [蓝桥杯 2024 省 A] 封印宝石

rekcA_h · 2026-03-05 22:42:40 · 题解

P10392 [蓝桥杯 2024 省 A] 封印宝石

P10392 [蓝桥杯 2024 省 A] 封印宝石

思路

看到字典序，显然贪心。枚举放的当前位置，每次在体力允许的情况下，尽可能地放魔力值较大的物品到当前位置。那任意两个相邻盒子不能存放魔力值相同的宝石如何满足呢？如果当前区间最大值与上一个位置的值一样，那我们就换成严格次大值就可以了。

线段树维护区间最大值和次大值，同时为了计算体力消耗，还要维护最大值以及次大值的下标。

代码

给出一个很丑的区间次大值实现。

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

struct Node{
    int mxpos,mx = INT_MIN,smxpos,smx = INT_MIN;
    Node operator+(const Node &x)const{
        Node res;
        if(mx >= x.mx){
            res.mx = mx;
            res.mxpos = mxpos;
        }
        else{
            res.mx = x.mx;
            res.mxpos = x.mxpos;
        }
        if(mx == x.mx){
            if(smx >= x.smx){
                res.smx = smx;
                res.smxpos = smxpos;
            }
            else{
                res.smx = x.smx;
                res.smxpos = x.smxpos;
            }
        }
        else{
            if(mx > x.mx){
                res.smx = max({x.mx,x.smx,smx});
                if(res.smx == smx) res.smxpos = smxpos;
                else if(res.smx == x.smx) res.smxpos = x.smxpos;
                else if(res.smx == x.mx) res.smxpos = x.mxpos;
            }
            else{
                res.smx = max({mx,x.smx,smx});
                if(res.smx == mx) res.smxpos = mxpos;
                else if(res.smx == smx) res.smxpos = smxpos;
                else if(res.smx == x.smx) res.smxpos = x.smxpos;
            }
        }
        return res;
    }
};

struct Segment_tree{
    int n;
    vector<Node> nodes;

    Segment_tree(const vector<Node> &arr){
        n = arr.size() - 1;
        nodes.resize(n * 4);
        build(1,1,n,arr);
    }

    void pushup(int p){
        nodes[p] = nodes[p<<1] + nodes[p<<1|1];
    }

    void build(int p,int l,int r,const vector<Node> &a){
        if(l == r){
            nodes[p] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(p<<1,l,mid,a);
        build(p<<1|1,mid + 1,r,a);
        pushup(p);
    }
    void update(int p,int l,int r,int d,const Node &x){
        if(l == r && l == d){
            nodes[p] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if(mid >= d) update(p<<1,l,mid,d,x);
        if(mid < d) update(p<<1|1,mid + 1,r,d,x);
        pushup(p);
    }
    Node query(int p,int l,int r,int d,int b){
        if(l >= d && r <= b){
            return nodes[p];
        }
        int mid = (l + r) >> 1;
        if(mid >= b) return query(p<<1,l,mid,d,b);
        if(mid < d) return query(p<<1|1,mid + 1,r,d,b);
        return query(p<<1,l,mid,d,b) + query(p<<1|1,mid + 1,r,d,b);
    }
};

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int> a(n + 1);
    for(int i = 1;i <= n;i++) cin>>a[i];
    vector<Node> nd(n + 1);
    for(int i = 1;i <= n;i++){
        nd[i].mx = a[i];
        nd[i].mxpos = i;
    }
    Segment_tree t(nd);
    vector<int> ans(n + 1,-1);
    for(int i = 1;i <= n;i++){
        auto [maxpos,maxn,smaxpos,smaxn] = t.query(1,1,n,i,min(n,i + k));
        if(maxn == INT_MIN) continue;
        if(ans[i-1] == maxn){
            if(smaxn == INT_MIN) continue;
            ans[i] = smaxn;
            t.update(1,1,n,smaxpos,{0,INT_MIN,0,INT_MIN});
            k -= smaxpos - i;
        }
        else{
            ans[i] = maxn;
            t.update(1,1,n,maxpos,{0,INT_MIN,0,INT_MIN});
            k -= maxpos - i;
        }
        if(k < 0){
            break;
        }
    }
    for(int i = 1;i <= n;i++) cout<<ans[i]<<' ';
    return 0;
}