AcWing 4961. 整数删除
原题链接
中等
作者:
YMYS
,
2024-04-04 11:29:18
,
所有人可见
,
阅读 23
注意:一定要要加#deinfe int long long,不然会损失大部分数据
//2024.4.4
//https://www.lanqiao.cn/student/saas/htm1/brush-questions/academy/48951/?bank_id=105&saas_id=412
//仿真真题,整数删除
/*
思路:每次找到最小值———>堆、每次在最小值的旁边两个值加上这个最小值的数值———>双向链表
*/
#pragma GCC target ("avx")
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5e5+10;
int n,k;//总共n个数,要删除k个数
//双向链表的基础结构
int e[N];//存值
int l[N];//l[i]:存i坐标对应的数的左端的值坐标
int r[N];//r[i]:存i坐标对应的数的右端的值坐标
//优先队列,这里做的是小根堆【PII的结构,第一个int存的是e[i]的值,第二个存的是e[i]对应的i。注意:这里因为会进行加操作,所以可能e[i]不是最初存的时候的e[i]】
priority_queue<PII, vector<PII>, greater<PII>> p;
//该函数的作用是:将在e[]数组中下标为x的的元素删掉,并将其左右两个元素加上这个e[x]
void rel(int x){
//删除e[i]
l[r[x]] = l[x];
r[l[x]] = r[x];
//加操作
e[l[x]] += e[x];
e[r[x]] += e[x];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>k;
//初始化双链表
r[0] = 1;
l[n+1] = n;
//输入操作
for(int i=1;i<=n;i++){
cin>>e[i];
l[i] = i-1;
r[i] = i+1;
p.push({e[i],i});
}
//进行k次题意操作
while (k--)
{
auto xx = p.top();//取最小值
p.pop();//弹出最小值
if(xx.first != e[xx.second]){//该e[i]发生了加操作,已经不是最小值了
p.push({e[xx.second], xx.second});//重新将新的e[i]加入到小根堆中
k++;
}else{
rel(xx.second);
}
}
//用双链表的方式,遍历剩下的所有数
int head = r[0];
while (head != n+1)
{
cout<<e[head]<<" ";
head = r[head];
}
return 0;
}