Visit Counter
AmazingCounters.com

1、题目大意:给一个序列t,然后求一个序列z,使得|z1-t1|+|z2-t2|+...+|zn-tn|的值最小,我们只需要求出这个值就可以了,并且z序列是递增的
2、分析:这道题z序列是递增的,不好做啊,我们想让z序列变成不降的,可以将t数组进行改变,就是t[i]-=i。不降的就好做多了,我们可以让一段下降的t序列对应的z序列全是中位数。但是我们还要维护z序列是单调的,于是我们从头扫,用一个单调栈,对于每一个t,先压进栈,如果栈顶元素的中位数比栈的第二个元素要小,就把栈顶和第二个元素合并,维护中位数。最后用这个栈中的元素算出z序列,最后就是求值了
3、代码:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1100000
#define LL long long
struct merge_heap{
    int l[M], r[M], d[M], value[M];
    void init(){
        memset(l, 0, sizeof(r));
        memset(r, 0, sizeof(r));
        memset(d, 1, sizeof(d));
    }
    int merge(int x, int y){
        if(!x) return y;
        if(!y) return x;
        if(value[x] < value[y]) swap(x, y);
        r[x] = merge(r[x], y);
        if(d[l[x]] < d[r[x]]){
            swap(l[x], r[x]);
        }
        d[x] = d[l[x]] + 1;
        return x;
    }
} wt; 
int L[M], R[M], tree[M], Size[M], Top = 0, t[M], z[M];
int main(){
    wt.init();
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);
    for(int i = 1; i <= n; i ++) t[i] -= i;
    for(int i = 1; i <= n; i ++){
        wt.value[i] = t[i];
        tree[++ Top] = i;
        L[Top] = R[Top] = i;
        Size[Top] = 1;
        while(Top > 1 && wt.value[tree[Top]] <= wt.value[tree[Top - 1]]){
            R[Top - 1] = R[Top];
            Size[Top - 1] += Size[Top];
            tree[Top - 1] = wt.merge(tree[Top - 1], tree[Top]);
            Top --;
            int len = R[Top] - L[Top] + 1;
            if(len % 2 == 0){
                len /= 2;
            }
            else{
                len = len / 2 + 1;
            }
            while(Size[Top] > len){
                Size[Top] --;
                tree[Top] = wt.merge(wt.l[tree[Top]], wt.r[tree[Top]]);
            }
        }
    }
    for(int i = 1; i <= Top; i ++){
        for(int j = L[i]; j <= R[i]; j ++){
            z[j] = wt.value[tree[i]];
        } 
    }
    LL ans = 0;
    for(int i = 1; i <= n; i ++){
        ans += (LL)(abs(z[i] - t[i]));
    }
    printf("%lld\n", ans);
    return 0;
}