东莞手机端建站模板,东莞常平汽车站时刻表,国外采购外贸交易平台,设计师平台网站4961. 整数删除 - AcWing题库
题目描述 分析
注#xff1a;如果要进行大量的删除操作可以使用链表
动态求最小值使用堆#xff0c;每次从堆中取出最小值的下标然后在链表中删除
注意long long
代码解释#xff1a; while(k --){auto t q.top();q.pop();res t.first;i…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 (因为这一步只是将上一步两边加数的操作进行了完善
#includebits/stdc.h
using namespace std;
const int N 5e5 10;
typedef long long ll;
typedef pairll, ll PII;
priority_queuePII, vectorPII, greaterPIIq;
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;
}
