蓝桥杯23年第十四届省赛-整数删除|STL优先队列、双向链表

题目链接：

蓝桥杯2023年第十四届省赛真题-整数删除 - C语言网 (dotcpp.com)

 0整数删除 - 蓝桥云课 (lanqiao.cn)

学习：蓝桥杯真题讲解：整数删除_蓝桥杯整数删除 c语言-CSDN博客 

说明：

在暴力做法里面，每次都要花费O（n）时间找最小值，再花O（n）时间找相邻的未被删除的元素。外层是k次删除。k*n的复杂度会超时。

于是考虑优化：每次只需要找最小值，不用完全排序，完全排序会把所有的大小顺序找出来，而我们不关注，因为会有相邻元素加上这个被删除的元素，原来的完全排序失去了参考意义，况且完全排序O(NlogN) 。所以选择堆排序，也就是优先队列，greater表示小顶堆，logn的复杂度。使用结构体第三个参数要自己实现仿函数。

类似：

struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;         
        return a.x> b.x; }
}

 参考学习：优先队列详解/C++-CSDN博客

排序时，值相同时，要比较索引，索引小的先删，所以队列的元素肯定要包括值和索引。并且，如果没有索引，就没办法知道它对应的位置是哪个，没办法找相邻的元素。故确定了优先队列的一个元素需要保存哪些信息。两个元素可以使用pair，保存值和它的位置索引。pair类型元素排序时先比较第一个元素，相同则比较第二个元素，符合题意，删除索引更小的最小元素。

要快速找出未被删除的相邻的元素，就要维护每个元素的相邻元素的坐标（前驱，后继）数组，逻辑上相当于一个双向链表 。每次删除元素时要做相应的更新。这样找 被删除的元素 的 未被删除的相邻的元素 的时间就降低到O(1)。

因为删除元素后，相邻元素更新后的值已经保存在数组st里。如果这个元素在队列里不会被排到队头，也就是不更新的值也不是最小的，不会影响优先队列取最小值，那么就不用再更新队列里的这个元素的值。所以一个if语句是否队头元素值等于它在数组的值判断就够了，确定是不是我没更新的那个元素排到队头来，如果是，需要更新值，再入队，重新调整堆，再取队头，确保取出最新的最小值。

小结

1.当只需要最值时，考虑用堆排序（优先队列）

2.相邻元素会变化时，需要快速找到相邻元素时，为每个元素 维护相邻下标，变化就更新。

代码部分

暴力代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
const int N =5e5+10;
int ans = 0;
int k;
int a[N];//原始数组，存原始数据 
int mn=1e8+1;
int mnj=-1;


signed main() {
 
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
   
    int n;
    cin>>n;
    cin>>k;
    
    for(int i=0;i<n;i++){
    	
    	cin>>a[i];
    	st[i]=a[i];
    	pq.push({a[i],i});
    	
    	l[i]=i-1;
		r[i]=i+1;
		
		if(i==n-1)
		r[i]=-1; 
    	
	}
    
    
    for(int i=1;i<=k;i++){
    	mn=1e8+1;
    	for(int j=0;j<n;j++){
    		if(mn>a[j]&&a[j]!=-1){
    			mn=a[j];
    			mnj=j;
			}
		}

    //暴力时需要注意的，
	//找相邻的元素时可能相邻的元素不止一个被删除了，要用while一直找到一个未被删除的 
		int lj=mnj;
		while(lj-1>=0&&a[lj-1]==-1){
			lj--;
		}
		if(lj-1>=0&&a[lj-1]!=-1) a[lj-1]+=a[mnj];
		
		int rj=mnj;
		while(rj+1<n&&a[rj+1]==-1){
			rj++;
		}
		
		if(mnj+1<n&&a[rj+1]!=-1){
			a[rj+1]+=a[mnj];
		}
    	a[mnj]=-1;
	}

    
    for(int i=0;i<n;i++){
    	if(a[i]!=-1)
    	cout<<a[i]<<' ';
	}
  
  return 0;
}

正解代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
const int N =5e5+10;
int ans = 0;
int k;
int a[N];//原始数组，存原始数据 
int mn=1e8+1;
int mnj=-1;

priority_queue<pii,vector<pii>,greater<pii>> pq; 
//链表的存储，用每个元素的前驱，后继来表示 
int l[N],r[N];//第i个元素的前驱，后继（左相邻，右相邻） 
 
int st[N];//标记是否被删除 .也可以用来临时存储  变化后的值 
signed main() {
 
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
   
    int n;
    cin>>n;
    cin>>k;
    
    for(int i=0;i<n;i++){
        
    //    cin>>a[i];
    //    st[i]=a[i];
    //pq.push({a[i],i});
    cin>>st[i];
        pq.push({st[i],i});
        
        l[i]=i-1;
        r[i]=i+1;
        
        if(i==n-1)
        r[i]=-1; 
        
    }
    
    
    while(k){
        pii t=pq.top();
        pq.pop();
        
        
        //该元素相邻元素被删除后没更新，更新后再加入队列重新排序， 这次循环因为没有找到实际的最小元素，没有删除，跳过本次循环 
        if(t.first!=st[t.second]){
           // a[t.second]=st[t.second]; 
            pq.push({st[t.second],t.second});
            continue;
        }
        
        //只有删除了元素，k才减 
        k--;
        int pos=t.second;
        
        
        //删除元素后要更新 相邻元素的 前驱后继，注意这里中括号里不能写pos-1，pos+1
        //有可能此时它的前驱后继已经不是原始的相邻元素了 
        //注意要判断它的前驱后继是否越界 
        if(r[pos]>=0)
        l[r[pos]]=l[pos];
        if(l[pos]>=0)
        r[l[pos]]=r[pos]; 
        
        if(l[pos]>=0)
        st[l[pos]] +=t.first;
        if(r[pos]>=0)
        st[r[pos]] +=t.first;
        
        //更新后或者没被更新过的 最小的数 删除 ，标记,打印时不再打印 
        st[pos]=-1;
    }


//如果最后用a数组来输出，还要排空队列，因为可能还存在没及时更新的元素，没更新之前他也足够大所以一直没被排到队头
//所以没被更新 
  //  while(!pq.empty()){
  //          pii t=pq.top();
  //       pq.pop();
        
  //       if(t.first!=st[t.second]){
  //           a[t.second]=st[t.second]; 
    //     }
  //  }
    
    for(int i=0;i<n;i++){
        if(st[i]!=-1)
        cout<<st[i]<<' ';
    }
  
  return 0;
}