车展 (Standard IO)

题意/Description:

       遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：
       L1 R1
       L2 R2
       …
       Lm Rm
       单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。
       为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人，所以只好对每个展台依次操作。每次展览结束后，展台高度自动恢复到初始高度。
       请告诉管理员为了举办所有展览，他最少需要花多少时间将展台调整好。

 

读入/Input：

       第一行为两个正整数n、m。
       第二行共n个非负整数，表示第i辆车展台的高度h[i]。
       接下来m行每行2个整数Li、Ri（Li≤Ri）。

 

输出/Output：

       一个正整数，调整展台总用时的最小值。

 

题解/solution：

       找出每个区间的中位数，用t，k表示每个区间比a[i]大或小的个数。如果区间有奇数个，则比中位数大或小的个数是相等的，即t，k是相等的；如果区间有偶数个，则比中位数大或小的个数相差为1，即abs(t-k)=1。

       用邻接表储存，注意要用int64！！！

       详情见程序。

 

代码/Code：

var
  n,mm,mid:longint;
  ans:int64;
  a,f:array [0..1001] of longint;
  num:array [0..1001,0..1,0..1001] of longint;
  m,use:array [0..1001,0..1001] of longint;
procedure init;
var
  i,j,k,t1,t2,t,x,y:longint;
begin
  readln(n,mm);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
    begin
      mid:=a[i];
      m[0,0]:=0;
      for j:=1 to n do
        begin
          if a[j]>mid then f[j]:=f[j-1]+1 else
            if a[j]<mid then f[j]:=f[j-1]-1 else
              f[j]:=f[j-1];
          m[j,0]:=0;
          m[j,1]:=0;
        end;
      for j:=0 to i do
        begin
          t:=f[i]-f[j];
          if t>0 then begin t1:=t; t2:=1; end else
            if t<0 then begin t1:=-t; t2:=0; end else
              begin t1:=0; t2:=0; end;
          inc(m[t1,t2]);
          num[t1,t2,m[t1,t2]]:=j+1;
        end;
      for j:=i to n do
        begin
          t:=f[j]-f[i];
          if t>0 then begin t1:=t; t2:=0; end else
            if t<0 then begin t1:=-t; t2:=1; end else
              begin t1:=0; t2:=0; end;
          for k:=1 to m[t1,t2] do
            use[num[t1,t2,k],j]:=mid;
        end;
    end;
  for i:=1 to mm do
    begin
      readln(x,y);
      if (y-x) mod 2=1 then mid:=use[x,y-1]
                       else mid:=use[x,y];
      for j:=x to y do
        ans:=ans+abs(a[j]-mid);
    end;
  write(ans);
end;

begin
  init;
end.