【NOIP2017练习】怎样打好隔膜（贪心，堆，带删除priority

题意：OI大师抖儿在夺得银牌之后，顺利保送pku。这一天，抖儿问长者：“我的手速虽然已经站在了人类的巅峰，但是打隔膜还是输。我换了很多队友，但是没有用。请问应该怎样打好隔膜？”
长者回答：“你啊，Too Young Too Simple,Sometimes Naive!不过你来看看这个游戏，或许对你有些帮助。”

这是一个类似星球大战的游戏。有n个星球排成一列，第i个星球和第i+1个星球存在一条耗时为1、可多次经过的航线。同时还存在m扇传送门，一扇由i到j的传送门可以瞬间将抖儿从第i个星球传送到第j个星球或从第j个星球传送到第i个星球，但是传送完毕后传送门会消失。此外，抖儿目前的资源可以额外建造不多于p扇传送门。

抖儿可以从任意一个星球出发，经过所有的航线和传送门至少一次，然后在任意一个星球结束。抖儿自然希望能在尽量短的时间内完成任务，请你帮忙计算答案。

对于所有的数据，保证n≤1e9，m≤100000，p≤100000

思路：LYY压轴题

pascal用堆实现带删除priority_queue

开两个堆，一个放被删除元素的堆，删除元素时将其复制放入

取堆顶时判断堆顶是否与删除堆的堆顶相同

因为此题元素有两个值，需要二次比较

写的神志模糊转C保平安

 type arr=record

           x:int64;

           y,t:longint;

          end;

 var q1,q2:array[..]of arr;

     d,du,x,y:array[..]of longint;

     pre,next:array[..]of longint;

     a:array[..]of int64;

     n,m,i,t,t1,t2,up,cnt1,cnt2,p,tmp,p1,p2,k:longint;

     ans:int64;

 procedure swap(var x,y:int64);

 var t:int64;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var i,j,t,mid:longint;

 begin

  i:=l; j:=r; mid:=d[(l+r)>>];

  repeat

   while mid>d[i] do inc(i);

   while mid<d[j] do dec(j);

   if i<=j then

   begin

    t:=d[i]; d[i]:=d[j]; d[j]:=t;

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 function hash(k:longint):longint;

 var l,r,mid:longint;

 begin

  l:=; r:=up;

  while l<=r do

  begin

   mid:=(l+r)>>;

   if d[mid]=k then exit(mid);

   if d[mid]<k then l:=mid+

    else r:=mid-;

  end;

 end;

 procedure ins(x:int64;y:longint);

 var t1,t2,t,tmp,k:longint;

 begin

  inc(cnt1);

  q1[cnt1].x:=x; q1[cnt1].y:=y;

  k:=cnt1;

  while (k>)and((x<q1[k>>].x)or(x=q1[k>>].x)and(y<q1[k>>].y)) do

  begin

   t:=k>>;

   t1:=q1[k].y; t2:=q1[t].y;

   swap(q1[k].x,q1[t].x);

   tmp:=q1[k].y; q1[k].y:=q1[t].y; q1[t].y:=tmp;

   k:=k>>;

  end;

 end;

 procedure del(x:int64;y:longint);

 var t1,t2,t,tmp,k:longint;

 begin

  inc(cnt2);

  q2[cnt2].x:=x; q2[cnt2].y:=y;

  k:=cnt2;

  while (k>)and((x<q2[k>>].x)or(x=q2[k>>].x)and(y<q2[k>>].y)) do

  begin

   t:=k>>;

   t1:=q2[k].y; t2:=q2[t].y;

   swap(q2[k].x,q2[t].x);

   tmp:=q2[k].y; q2[k].y:=q2[t].y; q2[t].y:=tmp;

   k:=k>>;

  end;

 end;

 begin

  readln(n,m,p);

  up:=; d[]:=; d[]:=n;

  for i:= to m do

  begin

   read(x[i],y[i]);

   inc(up); d[up]:=x[i];

   inc(up); d[up]:=y[i];

  end;

  qsort(,up);

  t:=up; up:=;

  for i:= to t do

   if d[i]<>d[up] then begin inc(up); d[up]:=d[i]; end;

  du[]:=; du[up]:=;

  for i:= to m do

  begin

   x[i]:=hash(x[i]);

   y[i]:=hash(y[i]);

   du[x[i]]:=du[x[i]] xor ;

   du[y[i]]:=du[y[i]] xor ;

  end;

  tmp:=; m:=;

  for i:= to up do

   if du[i]= then

   begin

    if tmp> then begin inc(m); a[m]:=d[i]-d[tmp]; end;

    tmp:=i;

   end;

  for i:= to m do

  begin

   //writeln(a[i]);

   ins(a[i],i);

   pre[i]:=i-;

   next[i]:=i+;

  end;

  t:=(m-) div -p;

  //writeln(t);

  for i:= to t do

  begin

   if cnt2> then

   begin

    t1:=; t2:=;

    while (q1[t1].x=q2[t2].x)and(q1[t1].y=q2[t2].y) do

    begin

     q1[t1].x:=<<;

     while t1<<<=cnt1 do

     begin

      k:=t1<<;

      if (k+<=cnt1)and((q1[k+].x<q1[k].x)or

                       ((q1[k+].x=q1[k].x)and(q1[k+].y<q1[k].y))) then inc(k);

      if q1[k].x<q1[t1].x then

      begin

       swap(q1[k].x,q1[t1].x);

       tmp:=q1[k].y; q1[k].y:=q1[t1].y; q1[t1].y:=tmp;

       t1:=k;

      end

       else break;

     end;

     q2[t2].x:=<<;

     while t2<<<=cnt2 do

     begin

      k:=t2<<;

      if (k+<=cnt2)and((q2[k+].x<q2[k].x)or

                       ((q2[k+].x=q2[k].x)and(q2[k+].y<q2[k].y))) then inc(k);

      if q2[k].x<q2[t2].x then

      begin

       swap(q2[k].x,q2[t2].x);

       tmp:=q2[k].y; q2[k].y:=q2[t2].y; q2[t2].y:=tmp;

       t2:=k;

      end

       else break;

     end;

     t1:=; t2:=;

    end;

   end;

   t2:=q1[].y; t1:=q1[].x;

   del(t1,t2);

   ans:=ans+t1;

   if pre[t2]= then

   begin

    p1:=next[t2];

   // writeln(p1);

    del(a[p1],p1);

    pre[next[next[t2]]]:=;

    continue;

   end

    else if next[t2]>m then

    begin

     p1:=pre[t2];

    // writeln(p1);

     del(a[p1],p1);

     next[pre[pre[t2]]]:=m+;

     continue;

    end;

   tmp:=t2;

   p1:=pre[tmp]; p2:=next[tmp];

  // writeln(p1,' ',p2);

   pre[tmp]:=pre[p1];

   next[tmp]:=next[p2];

   pre[next[tmp]]:=tmp;

   next[pre[tmp]]:=tmp;

   a[tmp]:=a[p1]+a[p2]-a[tmp];

   ins(a[tmp],tmp);

   del(a[p1],p1);

   del(a[p2],p2);

  end;

  writeln(ans+n-);

 end.

【后记】

抖儿深深沉迷于这个游戏不能自拔，日渐消瘦。

终于有一天，抖儿大彻大悟，说：“我知道了！玩游戏要的不仅仅是蛮力和手速，还需要智慧和策略。”

长者嘿嘿一笑：“你想多了。难道你还没发现你只适合玩单机游戏？”

抖儿恼羞成怒，便怂恿香港记者们造了一个大新闻，将长者批判了一番。

巴特西

【NOIP2017练习】怎样打好隔膜（贪心，堆，带删除priority_queue）

最新文章

热门文章