【题解 && 堆】 [蓝桥杯2023初赛] 整数删除

题目描述：

---

分析：

这道题一看就是一道堆的模板题
我们用堆记录当前的最小值以及当前值所在的下标
每次取出堆顶元素删除，而后将他的前一个以及后一个元素的值加上他的值就可以了
但是会有一个问题
你删除一个数之后，当前数左边和右边的两个数会加上当前这个数，你虽然把这两个数放到了堆里面，但是这个堆里面仍然存在着未加上被删数的这两个数。但是我们知道这两个数实际上已经不存在了，已经变成新的加上被删数的两个数了

怎么样可以跳过这两个原来的数呢？

我们可以对每一个位置记录一个时间戳
如果当前数被加上了新的数，那么加入堆之后就让这个位置的时间戳+1，最后取出堆顶元素的时候只需要比较当前堆顶元素的时间戳和当前位置的实际时间戳是否相同即可

---

#include
using namespace std;

#define int long long 

typedef pair < int , pair < int , int >> pii;
#define mp make_pair
const int N = 5e5+100;
int Ne[N] , La[N];
int n,K;
int a[N];
bool vi[N];
bool iss[N];
int now[N];

priority_queue < pii , vector < pii > , greater < pii > > q;

signed main(){
	scanf("%lld %lld",&n,&K);
	for (int i = 1; i <= n; i++)
	  scanf("%d",&a[i]),vi[i] = 1;
	for (int i = 1; i <= n; i++)
	  now[i] = 0,Ne[i] = i+1 , La[i] = i-1;
	for (int i = 1; i <= n; i++)
	  q.push(mp(a[i],mp(i,0)));
	int cnt = 0;
	while (q.size()){
		if (cnt == K) break;
		while (q.top().second.second!=now[q.top().second.first]) q.pop();
		int x = q.top().second.first , v = q.top().first;
		q.pop();
		if (iss[x]) {continue;}
		iss[x] = 1;
		if (vi[La[x]]) a[La[x]]+=a[x] , q.push(mp(a[La[x]],mp(La[x],++now[La[x]])));
		if (vi[Ne[x]]) a[Ne[x]]+=a[x] , q.push(mp(a[Ne[x]],mp(Ne[x],++now[Ne[x]])));
		Ne[La[x]] = Ne[x]; La[Ne[x]] = La[x];
		cnt++;
	}
	int k = 1;
	while (iss[k]) k++;
	while (k!=n+1) cout<<a[k]<<' ' , k = Ne[k];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43