蓝桥杯每日一题2023.9.23

4961. 整数删除 - AcWing题库

题目描述

 分析

注：如果要进行大量的删除操作可以使用链表

动态求最小值使用堆，每次从堆中取出最小值的下标然后在链表中删除

注意long long

代码解释：

	while(k --){auto t = q.top();q.pop();res = t.first;i = t.second;if(res != v[i])q.push({v[i], i});else del(i);	}

eg. 2 3 4此时这三个数的下标分别为1 2 3

第一步：在q的队列中加入2， 3， 4，第一次k --进行del操作，使v[2] == 5

第二部：q.top() == 3发现3对应下标为2， v[2]原本为3，但是上一步使其变为了5，故此时需要重新将5加入队列，当然，此时k不算进行了一次操作，需要k ++(因为这一步只是将上一步两边加数的操作进行了完善）

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
typedef pair<ll, ll> PII;
priority_queue<PII, vector<PII>, greater<PII>>q;
ll n, k, v[N], l[N], r[N];
void del(ll x)
{r[l[x]] = r[x], l[r[x]] = l[x];v[l[x]] += v[x], v[r[x]] += v[x];
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;r[0] = 1, l[n + 1] = n;//初始化左右端点的下标，将0后的下标赋于1，将n + 1左边的下标赋予n for(int i = 1; i <= n; i ++){cin >> v[i];//下标i对应的值为v[i]l[i] = i - 1;//建立双链表 r[i] = i + 1; q.push({v[i], i});//将值和对应下标存入优先队列 }while(k --){auto t = q.top();q.pop();ll res = t.first;ll i = t.second;if(res != v[i]){q.push({v[i], i});k ++;}else del(i);	}for(int i = r[0]; i != n + 1; i = r[i]){cout << v[i] << ' ';}cout << '\n';return 0;
}