蓝桥杯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;
}

相关推荐

  1. 大学B组(C/C++)整数删除

    2024-04-02 18:52:01       8 阅读
  2. 2023真题----棋盘

    2024-04-02 18:52:01       24 阅读
  3. 2023真题-阶乘求和

    2024-04-02 18:52:01       16 阅读

最近更新

  1. go下载依赖时超时timeout

    2024-04-02 18:52:01       0 阅读
  2. Ubuntu22.04.4 - MySQL8 - 笔记

    2024-04-02 18:52:01       0 阅读
  3. 如何管理一个团队,因为有些人他不听我的话?

    2024-04-02 18:52:01       0 阅读
  4. C++实战篇(一)——自旋锁的使用

    2024-04-02 18:52:01       0 阅读
  5. pinpoint接入及接入tomcat

    2024-04-02 18:52:01       0 阅读
  6. Git的SSH密钥配置

    2024-04-02 18:52:01       0 阅读
  7. pull获取最新代码

    2024-04-02 18:52:01       0 阅读

热门阅读

  1. MATLAB如何批量更改文件名

    2024-04-02 18:52:01       6 阅读
  2. 人工智能的实现流程

    2024-04-02 18:52:01       5 阅读
  3. Webshell网络安全应急响应概述

    2024-04-02 18:52:01       8 阅读
  4. Linux关机命令

    2024-04-02 18:52:01       6 阅读
  5. 冥想第一千一百一十七天

    2024-04-02 18:52:01       6 阅读
  6. 在linux上设置nginx上自动启动

    2024-04-02 18:52:01       6 阅读
  7. 第一章设计模式概述

    2024-04-02 18:52:01       5 阅读