code

用户名：wjh31415926535

访问量：972

签　名：

等　　级
排　　名	26280
经　　验	579
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

TA的其他文章

前驱后驱数组 + 优先队列
浏览：359

tarjan算法求lca
浏览：251

tarjan + lca + 树上差分
浏览：299

你可能喜欢

前驱后驱数组 + 优先队列

　　作者: code　　　　发表时间：2023-04-10 15:12:25 浏览：359　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-整数删除

# 思路
## 如何动态维护这个序列
对于这题我们需要维护一个前驱数组和后驱数组，当选中下标i作为被删除点时候进行如下操作
![](/image_editor_upload/20230410/20230410030355_21600.png)
```cpp
// 找到index 的前驱 sucs ，后驱 pres
	int sucs = suc[index];
	int pres = pre[index];
// 将sucs 的下一位更新为pres
	pre[sucs] = pres;
// 将pres 的前一位更新位sucs
	suc[pres] = sucs;
// 更新左右两边的数值（因为删除之后， 左右两边都要加上ans[index]
	ans[sucs] += ans[index];
	ans[pres] += ans[index];
// 如果后驱和前驱的下标都在【1 ~ n】的范围内，放入堆中
	if(sucs >= 1 && sucs <= n)q.push({ans[sucs], sucs});
	if(pres >= 1 && pres <= n)q.push({ans[pres], pres});
// 将它们访问次数增加，至于为什么会在下面解释
	vis[sucs]++;
	vis[pres]++;
// 被删除的点赋值为-1
	pre[index] = -1;
	suc[index] = -1;
```
## 那么我们该如何避免优先队列取出来的东西，是已经还未更新过的呢？
```cpp
// 当这个点vis次数大于等于1的时候， 我们就将vis减去1， 然后将这个数据弹出去，直到找到一个vis【】== 0的数据
while(vis[q.top().idx] >= 1){
	vis[q.top().idx]--;
	q.pop();
}
index = q.top().idx;
q.pop();
```
# 代码(可在本站ac)
```cpp
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <math.h>
#include <algorithm>
#include<numeric>
#include<ctime>
#include <cstring>
#define lowbit(x) (-x) & x
#define ll long long
using namespace std;    
struct node{
    ll val;
    int idx;
    friend bool operator<(const node& a, const node& b){
        if(a.val == b.val)return a.idx > b.idx;
        else return a.val > b.val;
    }
};
void solve(){
    int n,m;
    cin>>n>>m;
    ll ans[n + 1]; 
    for(int i = 1; i <= n;++i)cin>>ans[i];
    int pre[n+2];
    int suc[n+2];
    for(int i = 1; i <= n + 1;++i){
        pre[i] = i + 1;
        suc[i] = i - 1;
    }
    priority_queue<node>q;
    for(int i = 1; i <= n;++i){
        q.push({ans[i], i});
    }
    vector<int>vis(n + 2, 0);
    for(int i = 1; i <= m;++i){
        int mine = 0x7fffffff;
        int index = 1;
        while(vis[q.top().idx] >= 1){
            vis[q.top().idx]--;
            q.pop();
        }
        index = q.top().idx;
        q.pop();
        int sucs = suc[index];
        int pres = pre[index];
        pre[sucs] = pres;
        suc[pres] = sucs;
        ans[sucs] += ans[index];
        ans[pres] += ans[index];
        if(sucs >= 1 && sucs <= n)q.push({ans[sucs], sucs});
        if(pres >= 1 && pres <= n)q.push({ans[pres], pres});
        vis[sucs]++;
        vis[pres]++;
        pre[index] = -1;
        suc[index] = -1;
    }
    for(int i = 1; i <= n;++i){
        if(pre[i] == -1)continue;
        cout<<ans[i]<<" ";
    }
}   
int main(){ 
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int t;
    t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}

```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

code

TA的其他文章

你可能喜欢

【明明的随机数】（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-求偶数和（C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

前驱后驱数组 + 优先队列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

程序员的表白（C语言代码）

前10名（C语言代码）

神奇的fans （C语言代码）

剔除相关数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

简单的a+b （C语言代码）

code

TA的其他文章

你可能喜欢

【明明的随机数】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

Lucky Word （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

前驱 后驱数组 + 优先队列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

程序员的表白 （C语言代码）

前10名 （C语言代码）

神奇的fans （C语言代码）

剔除相关数 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

简单的a+b （C语言代码）

【明明的随机数】（C语言代码）

C二级辅导-求偶数和（C语言代码）

前驱后驱数组 + 优先队列

　　评论区

程序员的表白（C语言代码）

前10名（C语言代码）

剔除相关数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）