本文共 2082 字，大约阅读时间需要 6 分钟。

灯泡开关

题目链接：

题目大意

就是每次可以将一个数加一或者到达你设定的一个点。
如果加到 $m+1$ 就会变回一。

然后给你一个序列，数原来是序列的第一个数，然后要变换到第二个数，在变成第三个，直到最后一个。

然后要你求最少操作次数。

思路

很容易想到 $n^2$ 做法，就是枚举设定的点。

但是怎么优化呢？
考虑一开始不设点，然后设 $f_i$ 为设定的点设在 $i$ 会使答案减少多少步。

那我们看，如果要从 $x$ 走到 $y$，我们就来分类讨论。
如果你设的点是 $x$ 或者 $x+1$（如果加了超过 $m$ 自动 $-m$，下同），那直接走会设跳了再走一样，甚至更优。
那如果设的点 $x+2$ 或者之后，那就会分别省 $1,2,3,...$ 步，以此类推。

那要让一个序列加上一个等差序列，很容易就想到要用双重差分。
第一次，变成 $1,1,1,...,-(前面1的个数)$。
第二次，变成这个：
$1,0,0,...,-(上面的这一个+1),(前面的这个数-1)$

但是你会发现它可能会断开两节。
那右边那一节还好，左边一节又要重新搞。

假设这里是从 $i$ 开始。
那我们就开一个一重的差分数组，在第一位加 $i-1$，在最后一位的后面减回去，就可以变成跟上面一样都从一开始了。

最后把它还原，然后找到减少数量最大的。
然后就算出答案了。

代码

#include<cstdio>#include<iostream>using namespace std;int n, m, a[1000001], sum;long long ans, an, cf[1000001], cf2[1000001];long long getdis(int x, int y) {   	if (x < y) return (long long)(y - x);	return (long long)(y + m - x);}void work(int x, int y, int from, int add) {   	cf[x] += (long long)from;	cf[y + 1] -= (long long)from;	cf2[x + 1] += (long long)add;	cf2[y + 1] -= (long long)add * (long long)(y - x + 1);	cf2[y + 2] += (long long)add * (long long)((y - x + 1) - 1);}int main(){   	freopen("light.in", "r", stdin);	freopen("light.out", "w", stdout);		scanf("%d %d", &n, &m);	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);		for(int i = 2; i <= n; i++) {   		ans += getdis(a[i - 1], a[i]);				if (a[i] > a[i - 1]) {   			if (a[i] - a[i - 1] > 1) work(a[i - 1] + 2, a[i], 1, 1);		}		else {   			if (m - a[i - 1] > 1) {   				work(a[i - 1] + 2, m, 1, 1);				work(1, a[i], m - (a[i - 1] + 1) + 1, 1);			}			if (m - a[i - 1] == 1) {   				work(1, a[i], 1, 1);			}			if (m == a[i - 1] && a[i] > 1) work(2, a[i], 1, 1);		}	}		for (int i = 2; i <= m; i++) {   		cf[i] += cf[i - 1];		cf2[i] += cf2[i - 1];	}	for (int i = 2; i <= m; i++)		cf2[i] += cf2[i - 1];	for (int i = 1; i <= m; i++)		an = max(cf[i] + cf2[i], an);		printf("%lld", ans - an);		return 0;}