n方破百万 暴力踩标算

发现大家都是平衡树或者set.
这里介绍一种更为简单的方法.
我们直接先计算出前面两天的值.
后面的就可以直接枚举最小值,如果被标记了,就可以直接break.
速度比splay快了50ms.
不过要注意的是此题营业额可以为负,标记就需要多开一倍.

#include<bits/stdc++.h>
using namespace std;
const int M=2e6;
bool vis[5000000];
int n,s,x,y,t;
int main() {
    scanf("%d%d%d",&n,&x,&y);
    n-=2;
    s=abs(y-x)+x;
    vis[y+M]=vis[x+M]=1;
    for(; n--; vis[x+M]=1) {
        scanf("%d",&x);
        t=0;
        for(;; t++) {
            if(vis[x+M-t]||vis[x+M+t]) {
                s+=t;
                break;
            }
        }
    }
    printf("%d", s);
    return 0;
}