宿豫网站建设制作,nas服务器可以做网站吗,网站开发技术网站模板,百度手机端推广题目链接#xff1a;
蓝桥杯2023年第十四届省赛真题-整数删除 - C语言网 (dotcpp.com) 0整数删除 - 蓝桥云课 (lanqiao.cn)
学习#xff1a;蓝桥杯真题讲解#xff1a;整数删除_蓝桥杯整数删除 c语言-CSDN博客
说明#xff1a;
在暴力做法里面#xff0c;每次都要花费…题目链接
蓝桥杯2023年第十四届省赛真题-整数删除 - C语言网 (dotcpp.com) 0整数删除 - 蓝桥云课 (lanqiao.cn)
学习蓝桥杯真题讲解整数删除_蓝桥杯整数删除 c语言-CSDN博客
说明
在暴力做法里面每次都要花费On时间找最小值再花On时间找相邻的未被删除的元素。外层是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.相邻元素会变化时需要快速找到相邻元素时为每个元素 维护相邻下标变化就更新。 代码部分
暴力代码 #includebits/stdc.h
#define int long long
#define endl \n
using namespace std;
typedef pairint,int pii;
const int N 5e510;
int ans 0;
int k;
int a[N];//原始数组存原始数据
int mn1e81;
int mnj-1;signed main() {ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);int n;cinn;cink;for(int i0;in;i){cina[i];st[i]a[i];pq.push({a[i],i});l[i]i-1;r[i]i1;if(in-1)r[i]-1; }for(int i1;ik;i){mn1e81;for(int j0;jn;j){if(mna[j]a[j]!-1){mna[j];mnjj;}}//暴力时需要注意的//找相邻的元素时可能相邻的元素不止一个被删除了要用while一直找到一个未被删除的 int ljmnj;while(lj-10a[lj-1]-1){lj--;}if(lj-10a[lj-1]!-1) a[lj-1]a[mnj];int rjmnj;while(rj1na[rj1]-1){rj;}if(mnj1na[rj1]!-1){a[rj1]a[mnj];}a[mnj]-1;}for(int i0;in;i){if(a[i]!-1)couta[i] ;}return 0;
}
正解代码
#includebits/stdc.h
#define int long long
#define endl \n
using namespace std;
typedef pairint,int pii;
const int N 5e510;
int ans 0;
int k;
int a[N];//原始数组存原始数据
int mn1e81;
int mnj-1;priority_queuepii,vectorpii,greaterpii 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;cinn;cink;for(int i0;in;i){// cina[i];// st[i]a[i];//pq.push({a[i],i});cinst[i];pq.push({st[i],i});l[i]i-1;r[i]i1;if(in-1)r[i]-1; }while(k){pii tpq.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 post.second;//删除元素后要更新 相邻元素的 前驱后继注意这里中括号里不能写pos-1pos1//有可能此时它的前驱后继已经不是原始的相邻元素了 //注意要判断它的前驱后继是否越界 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 tpq.top();// pq.pop();// if(t.first!st[t.second]){// a[t.second]st[t.second]; // }// }for(int i0;in;i){if(st[i]!-1)coutst[i] ;}return 0;
}
