一、视频讲解

蓝桥杯真题讲解：整数删除

二、暴力代码

// 暴力模拟
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f
using namespace std;
const int N = 5e5 + 10;
int a[N];//存储元素
bool st[N];//标记某个数字是否被删除
void solve()
{int n, k; cin >> n >> k;for(int i = 0; i < n; i ++)cin >> a[i];for(int i = 0; i < k; i ++){int minv = INF;int pos = -1;//找最小值for(int j = 0; j < n; j ++){if(minv > a[j] && !st[j]){minv = a[j];pos = j;}}st[pos] = true;//对相邻的数字进行操作for(int j = pos - 1; j >= 0; j --){if(!st[j]){a[j] += minv;break;}}for(int j = pos + 1; j < n; j ++){if(!st[j]){a[j] += minv;break;}}}for(int i = 0; i < n; i ++){if(!st[i])cout << a[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);int t = 1;// cin >> t;while(t--)solve();
};

三、正解代码

//整数删除：优先队列 + 模拟链表
#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 a[N], l[N], r[N];
int st[N];
void solve()
{int n, k; cin >> n >> k;priority_queue<pii, vector<pii>, greater<pii>>q;for(int i = 0; i < n; i ++){cin >> a[i];q.push({a[i], i});st[i] = a[i];l[i] = i - 1;r[i] = i + 1;if(r[i] == n)r[i] = -1;}int cnt = k;while(k){pii t = q.top();q.pop();if(t.first != st[t.second]){q.push({st[t.second], t.second});continue;}k --;//获取该元素在原数组中的位置int pos = t.second;//将该元素的相邻元素加上该数值if(l[pos] >= 0)st[l[pos]] += t.first;if(r[pos] >= 0)st[r[pos]] += t.first;//更新相邻点的相邻元素if(l[pos] >= 0)r[l[pos]] = r[pos];if(r[pos] >= 0)l[r[pos]] = l[pos];//该元素已经被删除，打标记st[pos] = -1;}for(int i = 0; i < n; i ++){if(st[i] != -1)cout << st[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while(t--)solve();
}