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;
}