SP1553题解

· · 题解

题面

本题不算太难，方法与 [国家集训队]种树 类似，我们通过双向链表维护数列，优先队列求最值。

我们设 nxt_i 表示链表中编号为 i 的元素的下一个元素的编号，per_i 表示链表中编号为 i 的元素的上一个元素的编号，a_i 表示链表中编号为 i 的元素的值。

当我们从优先队列中取出一个值时，把它累加进答案后，就表示我们选了这棵树。那么它两边的树就都不能选了。但是，有可能选两边会更优。

这时，代码的精髓就来了：“后悔处理”。如果现在我们选了 i，那我们就可以 a_i 变为 a_{per_i}+a_{nxt_i}-a_i。不难发现，如果我们选了这个新的 i 那么就相当于我们选了 per_i 和 nxt_i，而没选 i。

代码

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  int t,n,m,ans,a[100005];
  int l[100005],nxt[100005],per[100005];//链表
  struct node{
      int a,x;
      node(){}
      node(int c,int d){a=c,x=d;}
      bool operator<(const node &t)const{//重载运算符
          return a>t.a;
      }
  };
  priority_queue<node>q;
  bool vis[100005];//判断一个元素有没有被删除
  signed main()
  {
      scanf("%d",&t);
      while(t--){
          ans=0;
          memset(vis,0,sizeof(vis));
          while(!q.empty())q.pop();//清空
          scanf("%lld%lld",&n,&m);
          for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
          for(int i=1;i<n;i++)q.push(node(a[i+1]-a[i],i));
          for(int i=1;i<n;i++)nxt[i]=i+1,per[i]=i-1,l[i]=a[i+1]-a[i];n--;//初始化链表、优先队列
          l[0]=l[n+1]=INT_MAX;//将两边设为极大值，防止影响答案
          while(m--){
              while(vis[q.top().x])q.pop();
              node tmp=q.top();
              q.pop();
              vis[nxt[tmp.x]]=vis[per[tmp.x]]=1;//标记（就是这个）
              ans+=tmp.a;//累加答案
              tmp.a=-tmp.a+l[nxt[tmp.x]]+l[per[tmp.x]];//修改tmp.a的值为-tmp.a+l[nxt[tmp.x]]+l[per[tmp.x]]（后悔处理）
              l[tmp.x]=tmp.a;
              per[nxt[nxt[tmp.x]]]=tmp.x;
              nxt[tmp.x]=nxt[nxt[tmp.x]];
              nxt[per[per[tmp.x]]]=tmp.x;
              per[tmp.x]=per[per[tmp.x]];//删除两边的元素
              q.push(tmp);
          }
          printf("%lld\n",ans);
      }
      return 0;
  }

md，写题解的时候为了美观调换了几行的位置，结果挂了，警钟长鸣。