首页 > 代码库 > CH Round #45 能量释放

CH Round #45 能量释放

2024-07-16 04:00:22   220人阅读

能量释放 CH Round #45 - alan有一些陷阱 III

题目描述

    alan得到一块由$N$个能量晶体构成的矿石，对于矿石中的每一个能量晶体，如果用化学物质刺激某一个能量晶体，就能使它释放能量。

    它的能量释放强度与晶体本身的能量值$A_{i}$以及能量晶体的位置$i$有关。

    为了方便研究，alan做了如下的定义。

    $\bullet$能量集：一块矿石中的第$i$个能量晶体到第$j$个能量晶体（包含$i$和$j$，$1\leq i \leq j \leq N$）构成的集合。

    $\bullet$能量储存点：对于一块矿石中的能量晶体$i$和$j(i \neq j)$,若有$A_{j} \geq A_{i}$，则称$j$是$i$能量储存点。

    $\bullet$能量释放点：在一个能量集中，若存在一个能量晶体，使得除它之外的所有能量晶体都是它的能量储存点，则称这个能量晶体是该能量集的能量释放点。

    $\bullet$能量释放强度：对于一个能量集中的能量释放点来说，刺激这个能量晶体，该能量集中其余能量晶体会释放能量。该能量集的能量释放强度就等于该能量集中其余某个能量晶体的能量值与能量释放点的能量值的差的最大值。而第$i$个能量晶体的能量释放强度则是$i$所在的所有能量集的能量释放强度的最大值。

    alan将给出矿石中能量晶体的个数$N$，以及每个能量晶体的能量值$A_{i}$，要求你求出每个能量晶体的能量释放强度。

输入格式

    第一行1个整数$N$，表示矿石中能量晶体的个数。

    第二行$N$个整数，第$i$个整数表示第$i$个能量晶体的能量值$A_{i}$。

输出格式

    仅包含一行$N$个整数，第$i$个整数表示第$i$个能量晶体的能量释放强度。

样例输入

53 2 1 2 3

样例输出

0 1 2 1 0

数据范围与约定

  

  • 对于20%的数据:$1 \leq N \leq 1000$。
  • 对于60%的数据:$1 \leq N \leq 300000$。
  • 对于100%的数据:$1 \leq N \leq 2000000,0 \leq |A_{i}| \leq 2 \times 10^{9}$。
  • 温馨提醒：本题数据量较大，请尽量使用输入输出优化。

题解：
在考场上我写的是O（n）的单调队列（其实也相当于是单调栈。。。）+O（nlogn）的rmq
自己为能AC，结果只有一半
后来才知道如果数据规模达到百万以上，就一定得用O（n）的算法了，我还是太年轻啊。。。
今天准备做NOI2005瑰丽的华尔兹时，又用到了单调队列，忽然对这题有了想法，就又来做

这次我的算法，均摊应该是O（n）的吧。。。我想是这样。。。

其实考虑到a[i]左边的元素如果比a[j]小的话，那 j 管辖的范围 i 也也一定可以，(j 的初始值为 i-1）

所以我们直接跳到 j 管辖的范围的左边即可，即 j=l[j]-1 同时用 它来更新f[i]

最后跳不动的时候，j+1就是 l[i]

右边类似。。。

不知到复杂度是多少？怎么估计？求大神指教

自测稍有超时，后几个点都是1.2s左右的样子

代码：

1.考场 跑完所有数据需要 22s

 1 var  i,j,n,h,t:longint; 2      f:array[0..2000000+10,0..20] of longint; 3      a,q,l,r:array[0..2000000+10] of longint; 4   procedure init; 5    begin 6      readln(n); 7      for i:=1 to n do read(a[i]); 8    end; 9  procedure queue;10    begin11      a[0]:=-2100000000;a[n+1]:=a[0];12      fillchar(q,sizeof(q),0);13      h:=0;t:=0;14      for i:=1 to n+1 do15       begin16         while (h<t) and (a[i]<a[q[t]]) do17            begin18              r[q[t]]:=i-1;19              dec(t);20            end;21         inc(t);q[t]:=i;22       end;23      fillchar(q,sizeof(q),0);24      h:=0;t:=0;25      for i:=n downto 0 do26        begin27          while (h<t) and (a[i]<a[q[t]]) do28            begin29              l[q[t]]:=i+1;30              dec(t);31            end;32          inc(t);q[t]:=i;33        end;34      end;35 function max(x,y:longint):longint;36  begin37    if x>y then exit(x) else exit(y);38  end;39 40 procedure rmq;41   begin42     fillchar(f,sizeof(f),127);43     for i:=1 to n do f[i,0]:=a[i];44     for i:=1 to 22 do45      begin46        if (1<<i)>n then break;47        for j:=1 to n-(1<<i)+1 do48         f[j,i]:=max(f[j,i-1],f[j+1<<(i-1),i-1]);49      end;50   end;51 function query(x,y:longint):int64;52  var k:longint;53  begin54   k:=trunc(ln(y-x+1.0)/ln(2.0));55   exit(max(f[x,k],f[y-(1<<k)+1,k]));56  end;57 58 procedure main;59   begin60     queue;61     rmq;62   //  for i:=1 to n do writeln(l[i],‘ ‘,r[i]);63     for i:=1 to n do64       write(query(l[i],r[i])-a[i],‘ ‘);65   end;66 begin67   assign(input,‘input.txt‘);assign(output,‘output.txt‘);68   reset(input);rewrite(output);69   init;70   main;71   close(input);close(output);72 end.73
View Code

2.20140806 跑完所有数据需要 6s

 1 {$inline on} 2 const maxn=2000000+100; 3 var l,r,a,f:array[0..maxn] of longint; 4     i,n,j:longint; 5     function max(x,y:longint):longint;inline; 6      begin 7        if x>y then exit(x) else exit(y); 8      end; 9 10 procedure init;11  begin12    readln(n);13    for i:=1 to n do begin read(a[i]);f[i]:=a[i];end;14  end;15 procedure main;16  begin17    a[0]:=-maxlongint;a[n+1]:=-maxlongint;18    l[1]:=1;19    for i:=2 to n do20     begin21     j:=i-1;22     while a[i]<=a[j] do23      begin24      if f[j]>f[i] then f[i]:=f[j];25      j:=l[j]-1;26      end;27     l[i]:=j+1;28     end;29    r[n]:=n;30    for i:=n-1 downto 1 do31     begin32     j:=i+1;33     while a[i]<=a[j] do34      begin35      if f[j]>f[i] then f[i]:=f[j];36      j:=r[j]+1;37      end;38     r[i]:=j-1;39     end;40    for i:=1 to n-1 do write(f[i]-a[i],‘ ‘);writeln(f[n]-a[n]);41   end;42 begin43   assign(input,‘input.txt‘);assign(output,‘output.txt‘);44   reset(input);rewrite(output);45   init;46   main;47   close(input);close(output);48 end.
View Code

 


联系
我们