HYSBZ 1588 營業額統計

Description

營業額統計 Tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計并分析公司成立以來的營業情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由于節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況： 該天的最小波動值 當最小波動值越大時，就說明營業情況越不穩定。 而分析整個公司的從成立到現在營業情況是否穩定，隻需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程式幫助Tiger來計算這一個值。 第一天的最小波動值為第一天的營業額。  輸入輸出要求

Input

第一行為正整數 ，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數(有可能有負數) ，表示第i天公司的營業額。

Output

輸出檔案僅有一個正整數，即Sigma(每天最小的波動值) 。結果小于2^31 。

Sample Input

6
5
1
2
5
4
6      

Sample Output

12      

Hint

結果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

此題資料有問題，詳見讨論版http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1588

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 3e5 + 10;
int n, m, root, ans, x;

struct Splays
{
  const static int maxn = 3e5 + 10;     //節點個數
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右兒子，父親節點和節點總個數
  int A[maxn];
  int Node(int f, int u) { ch[sz][0] = ch[sz][1] = 0; F[sz] = f; A[sz] = u; return sz++; }//申請一個新節點
  void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; }//清空操作
  void rotate(int x, int k)
  {
    int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
    if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
    F[x] = F[y];    F[y] = x; ch[x][k] = y;
  }
  void Splay(int x, int r)
  {
    for (int fa = F[r]; F[x] != fa;)
    {
      if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
      int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
      y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
    }
  }
  int insert(int&x, int y)
  {
    if (!x) { x = Node(0, y); return y; }
    for (int i = x; i; i = ch[i][A[i] < y])
    {
      if (A[i] == y) { Splay(i, x); x = i; return 0; }
      if (!ch[i][A[i] < y])
      {
        i = ch[i][A[i] < y] = Node(i, y);
        Splay(i, x); x = i; break;
      }
    }
    int ans = INF;
    for (int i = ch[x][0]; i; i = ch[i][1])
    {
      ans = min(ans, y - A[i]);
    }
    for (int i = ch[x][1]; i; i = ch[i][0])
    {
      ans = min(ans, A[i] - y);
    }
    return ans;
  }
}solve;

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    solve.clear();  ans = root = 0;
    while (n--)
    {
      if (scanf("%d", &x) != 1) x = 0;//資料問題
      ans+=solve.insert(root, x);
    }
    printf("%d\n", ans);
  }
  return 0;
}