题目描述

整数删除 （有注释版）
小根堆 + 双向链表
必须开o2优化 否则有几个数据过不了

C++ 代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

#define x first
#define y second

typedef long long LL;
typedef pair<LL,int> PII;
const int N = 5e5 + 10;

LL cnt[N];  //下标为i的这个点需要加多少
bool st[N];  //标志这个数有没有被删除
int n,k;
int pre[N],ne[N];
LL s[N];

void del(int x)  //删除这个点
{
  int l = pre[x],r = ne[x];  
  st[x] = true;  //标记这个点已经删除
  cnt[l] += s[x];  
  cnt[r] += s[x];
  ne[l] = r;
  pre[r] = l;
}

int main()
{
  cin>>n>>k;

  priority_queue<PII,vector<PII>,greater<PII>>heap;
  for(int i = 1;i <= n;i ++)
  {
    cin>>s[i];  //输入当前的值
    pre[i] = i - 1;  //标记当前位置的前一个位置
    ne[i] = i + 1;  //标记当前位置的后一个位置
    heap.push({s[i],i});  //将当前的值和位置放入堆中
  }

  int g = n - k;  //这个队列最后应该有长度g
  while(heap.size() > g)
  {
    auto t = heap.top();  //取出该队列中最小的数
    heap.pop();

    LL v = t.x, id = t.y;
    if(cnt[id])  //如果这个最小的数还有加的值 就先加上这个值 再放入堆中 
    {            //至于最开始的这个值 到下一次循环时cnt = 0自然会删掉
      s[id] += cnt[id];
      heap.push({s[id],id});
      cnt[id] = 0;
    }
    else  //如果这个最小的数没有加的值 那么他就是最小的数 直接把他在双向链表中删掉
    {
      del(id);
    }
  }

  vector<LL>vec(n + 1);
  for(int i = 0;i < g;i ++)
  {
    auto t = heap.top();
    heap.pop();
    vec[t.y] = t.x + cnt[t.y];
  }

  for(int i = 1;i <= n;i ++)  //遍历的是整个双向链表
   if(!st[i]) cout<<vec[i]<<" ";
}