3774. 亮灯时长

题目链接

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 100050;
int t;
int a[M], b[M];
int maxx;
int main() {cin >> t;while (t--) {int n, m;cin >> n >> m;memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);n++;a[n] = m;for (int i = n - 1; i >= 0; --i)b[i] = b[i + 2] + a[i + 1] - a[i];maxx = b[0];for (int i = 0; i < n; ++i) {if (a[i + 1] - a[i] <= 1)continue;int k = a[i + 1] - a[i] - 1;if (i & 1) {maxx = max(maxx, b[i + 2] + k + b[0] - b[i + 1]);} else {maxx = max(maxx, b[i + 1] + k + b[0] - b[i]);}}cout << maxx << endl;}return 0;
}

题解：用前缀和的变形后缀和，分别计算出关灯和开灯的后缀时间总和，然后奇偶区间进行拨动开关，奇偶区间拨动开关的原理相同，都是区间前一段开灯时间总和加上区间后面开灯时间总和再加上当前区间开灯时间总和