题目描述

营业额统计 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况: 该天的最小波动值 当最小波动值越大时,就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。  输入输出要求

输入

第一行为正整数 ,表示该公司从成立一直到现在的天数,接下来的n行每行有一个整数(有可能有负数) ,表示第i
天公司的营业额。
天数n<=32767,
每天的营业额ai <= 1,000,000。
最后结果T<=2^31

输出

输出文件仅有一个正整数,即Sigma(每天最小的波动值) 。结果小于2^31 。

样例输入

6
5
1
2
5
4
6

样例输出

12

提示

结果说明:5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

该题数据bug已修复.----2016.5.15

题解

裸的Treap,对于每一天的最小波动值,是当天的值与前几天的某天中比当天值小且最大,或者比当天值大且最小的值做差取绝对值中最小的值。用 Treap 可以方便的维护前驱和后继。

代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Node {
    Node *ch[2]; //左右子树的指针
    int r; //优先级
    int v; //值

    //判断 x 是否比当前点的值大
    int cmp(int x) const {
        if(x == v) return -1;
        return x > v;
    }

    bool hasLeft() {
        return ch[0] != NULL;
    }

    bool hasRight() {
        return ch[1] != NULL;
    }
};

// d=0 代表左旋,d=1 代表右旋
void rotate(Node* &o, int d) {
    Node* k = o->ch[d^1];
    o->ch[d^1] = k->ch[d];
    k->ch[d] = o;
    o = k;
}

bool contains(Node* o, int x) {
    while(o != NULL) {
        int d = o->cmp(x);
        if(d == -1) return true;
        else o = o->ch[d];
    }
    return false;
}

void insert(Node* &o, int x) {
    if(contains(o, x)) return;
    // 新建节点
    if(o == NULL) {
        o = new Node();
        o->ch[0] = o->ch[1] = NULL;
        // 赋值并给予随机优先级
        o->v = x;
        o->r = rand();
    } else {
        int d = o->cmp(x);
        insert(o->ch[d], x);
        // 保证堆性质
        if(o->ch[d] ->r > o->r) rotate(o, d^1);
    }
}

int findmax(Node* o, int x) {
    if (o == NULL) return INF;
    if (x >= o->v) return findmax(o->ch[1], x);
    else return min(o->v, findmax(o->ch[0], x));
}

int findmin(Node* o, int x) {
    if (o == NULL) return -INF;
    if (x <= o->v) return findmin(o->ch[0], x);
    else return max(o->v, findmin(o->ch[1], x));
}

Node *tree;

int main() {
    int n; scanf("%d", &n);
    int ans = 0;
    for(int i=1; i<=n; i++) {
        int x; scanf("%d", &x);
        if(contains(tree, x)) continue;
        insert(tree, x);
        int mx = findmax(tree, x);
        int mn = findmin(tree, x);
        if(mx + mn == 0) {
            ans += x;
            //printf("add: %d\n", x);
        } else {
            //printf("add: %d\n", min(abs(x-mx), abs(x-mn)));
            ans += min(abs(x-mx), abs(x-mn));
        }
        //printf("%d %d\n", mx, mn);
    }
    printf("%d\n", ans);
    return 0;
}