atcode E - guruguru（思维+前缀）

题目链接：http://arc077.contest.atcoder.jp/tasks/arc077_c

题解：一道思维题。不容易想到类似区间求和具体看一下代码。

#include <iostream>

#include <cstring>

#include <cstdio>

#define inf 0X3f3f3f3f

using namespace std;

const int M = 1e5 + 10;

typedef long long ll;

int a[M];

ll add[M] , del[M];//add[i]表示取大于i的数为x时所需要的价值最小是多少，当然add是要结合del的del是类似于遍历i之后的数

int main() {

    int n , m;

    scanf("%d%d" , &n , &m);

    for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]);

    for(int i = 1 ; i < n ; i++) {

        int x = a[i] , y = a[i + 1];

        if(x < y) {

            add[1] += (y - x);

            add[x + 1] -= (y - x);

            del[x + 1]--;

            add[y + 1] += (y - x);

            add[x + 1] += y + 1;

            del[y + 1]++;

            add[y + 1] -= y + 1;

        }

        else if(x > y) {

            add[1] += y + 1;

            del[1]--;

            add[y + 1] -= y + 1;

            add[y + 1] += m - x + y;

            del[y + 1]++;

            add[x + 1] -= m - x + y;

            add[x + 1] += y + 1 + m;

            del[x + 1]--;

        }

        //这些处理都是可以想到的。就是在3个范围内(1~x,x~y,y~m)or(1~y,y~x,x~m)注意前一个区间加上去之后下个区间要减去。由于还与区间中取什么数有关所以引入了del

    }

    add[0] = 0 , del[0] = 0;

    for(int i = 1 ; i <= m ; i++) {

        add[i] += add[i - 1];

        del[i] += del[i - 1];

        //这种区间求和也可以利用这种方法来处理，或者使用其他数据结构的知识

    }

    ll ans = 1e12;

    for(int i = 1 ; i <= m ; i++) {

        ans = min(ans , add[i] + (ll)i * del[i]);

    }

    printf("%lld\n" , ans);

    return 0;

}