AtCoder Regular Contest 077 E

题目链接

题意

灯有(m)个亮度等级，(1,2,...,m)，有两种按钮：

每次将亮度等级(+1)，如(1 ightarrow 2,2 ightarrow 3,...,m-1 ightarrow m,m ightarrow 1)
初始时有一个设定值(x)，按下该按钮能够从任意亮度等级到达(x)

现给定一个序列(a[1..n])代表亮度从(a_1 ightarrow a_2 ightarrow a_3 ightarrow ... ightarrow a_n)，问初始值(x)设定为多少的时候能够使总共需按按钮的次数最少？

思路

原始思路

从(1)到(m)枚举(x)，对于每个(x)遍历一遍序列，计算出操作次数。

比较得到一个最小值。时间复杂度(O(m*n))

本质=>优化

思考一下，上面这个思路本质上是什么？

假设我们有一个数组(c[1..m])用来记录操作次数，那么其初始值为(0)，遍历一遍序列，对每个初始值(x)对应的操作次数(c[x])加上(f(a_i,a_{i+1},x)).

最后，(c[ ])数组的最小值即为答案。

再来考虑一下上面的(f(a_i,a_{i+1},x))，这又是什么？

记(s=a_i,t=a_{i+1})，不妨设(slt t)则$$f(s,t,x)=
egin{cases}
t-s, &xleq s || xgt tcr
t-x+1, &slt x leq t
end{cases}$$

// 高兴一下，是个线性函数啊

变化量如图所示：

1			s s+1		  t t+1		   m
|------------|------------|------------|
(	+t-s	) (	 +s-x+1	  )(	+t-s	)

仔细观察发现可以发现它可以拆成两部分

1									   m
|--------------------------------------|
(					+t-s				)

1			s s+1		  t t+1		   m
|------------|------------|------------|
(	+0		) (	 +t-x+1	  )(	+0		)

即

整体加上(t-s)
对([s+1,t])一段加上一个递减的序列。

整体的加直接记录即可，对一段进行的修改怎么办呢？
仔细观察这个递减的序列，发现其是({0,-1,-2,...,s-t+1})，于是可以借助前缀和(O(1))完成这个修改。
// 详见后文

于是我们的优化就完成了，成功从(O(n*m))变成(O(n)).

附

对于(sgt t)的情况，只需将(s)加上(m)考虑即可，就相当于将每个位置拆成两个。

前缀和大法

对区间([s,t])中的元素分别加上({1,2,...,n})，要求操作后的序列，方法为：

a[s] += 1, a[t+1] -= (n+1), a[t+2] += n;

求两次前缀和即得操作后的序列。容易验证。

Code

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long LL;
LL c[maxn], a[maxn];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    LL base = 0;
    for (int i = 1; i < n; ++i) {
        LL s = a[i-1], t = a[i];
        if (t < s) t += m;
        base += t - s;
        c[s+2] += 1, c[t+1] -= t-s, c[t+2] += t-s-1;
    }
    for (int i = 1; i <= (m<<1); ++i) c[i] += c[i-1];
    for (int i = 1; i <= (m<<1); ++i) c[i] += c[i-1];
    LL maxx = 0;
    for (int i = 1; i <= m; ++i) maxx = max(maxx, c[i] + c[i+m]);
    printf("%lld
", base - maxx);
    return 0;
}