TURNOVER.PAS 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
  1. {$S-,Y-,Q-,R-}
  2. program turnover;
  3. {This program was written by tiger.lee}
  4. const
  5. InputFileName = 'turnover.in';
  6. OutputFileName = 'turnover.out';
  7. type
  8. Pnode = ^Tnode;
  9. Tnode = object
  10. key: Longint;
  11. h: Integer;
  12. l, r: Pnode;
  13. end;
  14. var
  15. n, i: Integer;
  16. x, answer, min: Longint;
  17. tree: Pnode;
  18. procedure insertNode(const x : Longint;var node : Pnode);
  19. var
  20. p, temp, child: Pnode;
  21. lh, rh: Integer;
  22. tmp: Longint;
  23. procedure regulateLL;
  24. begin
  25. temp := node^.l;
  26. node^.h := temp^.h - 1;
  27. node^.l := temp^.r;
  28. temp^.r := node;
  29. node := temp;
  30. end;
  31. procedure regulateLR;
  32. begin
  33. child := node^.l;
  34. child^.h := child^.h - 1;
  35. node^.h := child^.h;
  36. temp := child^.r;
  37. temp^.h := child^.h + 1;
  38. child^.r := temp^.l;
  39. node^.l := temp^.r;
  40. temp^.r := node;
  41. temp^.l := child;
  42. node := temp;
  43. end;
  44. procedure regulateRR;
  45. begin
  46. temp := node^.r;
  47. node^.r := temp^.l;
  48. node^.h := temp^.h - 1;
  49. temp^.l := node;
  50. node := temp;
  51. end;
  52. procedure regulateRL;
  53. begin
  54. child := node^.r;
  55. child^.h := child^.h - 1;
  56. node^.h := child^.h;
  57. temp := child^.l;
  58. temp^.h := child^.h + 1;
  59. child^.l := temp^.r;
  60. node^.r := temp^.l;
  61. temp^.l := node;
  62. temp^.r := child;
  63. node := temp;
  64. end;
  65. begin
  66. if node = nil then begin
  67. New(p);
  68. p^.l := nil;
  69. p^.r := nil;
  70. p^.h := 1;
  71. p^.key := x;
  72. node := p;
  73. answer := answer + min;
  74. Exit;
  75. end;
  76. tmp := abs(node^.key - x);
  77. if tmp < min then min := tmp;
  78. if x <= node^.key then insertNode(x, node^.l)
  79. else insertNode(x, node^.r);
  80. if node^.l = nil then lh := 0 else lh := node^.l^.h;
  81. if node^.r = nil then rh := 0 else rh := node^.r^.h;
  82. if lh - rh = 2 then begin
  83. if node^.l^.l = nil then lh := 0 else lh := node^.l^.l^.h;
  84. if node^.l^.r = nil then rh := 0 else rh := node^.l^.r^.h;
  85. if lh - rh = 1 then regulateLL
  86. else regulateLR;
  87. Exit;
  88. end;
  89. if lh - rh = -2 then begin
  90. if node^.r^.l = nil then lh := 0 else lh := node^.r^.l^.h;
  91. if node^.r^.r = nil then rh := 0 else rh := node^.r^.r^.h;
  92. if lh - rh = -1 then regulateRR
  93. else regulateRL;
  94. Exit;
  95. end;
  96. if lh > rh then node^.h := lh + 1 else node^.h := rh + 1;
  97. end;
  98. begin
  99. Assign(Input, InputFileName);
  100. Reset(Input);
  101. Readln(n);
  102. Readln(answer);
  103. insertNode(answer, tree);
  104. for i := 2 to n do begin
  105. Readln(x);
  106. min := MaxLongint;
  107. insertNode(x, tree);
  108. end;
  109. Close(Input);
  110. Assign(Output, OutputFileName);
  111. Rewrite(Output);
  112. Writeln(answer);
  113. Close(Output);
  114. end.