Light It Up（思维）解析

Light It Up（思维）解析

有一盏灯，0时刻开着。n次操作，你可以在其中加入一次操作（或者不加），操作为：a[i]时刻按一下开关，状态变为相反状态（开->关or关->开）。问灯亮着的时长最长为多少？
保证a[i-1] 3 10
4 5 7
0~4开（时长为4-0），4~6关（时长为6-4），6~7开（时长为7-5），7~10关（时长为10-7）
我们可以在第3个时刻操作一下开关，过程变为：0~3开（时长为3-0），3~4关（时长为4-0），4~6开（时长为6-4），5~7关（时长为7-5），7~10开（时长为10-7），3+2+3=8

题解

比如第一个样例：开关灯时长为：4(开) 1(关) 2(开) 3(关) ，我们加一次操作相当于把某个数字拆成两个，肯定为一开一关，我们肯定让开最大（即该数字-1），拆完之后的开灯时长为：该数字之前的总开灯时长+该数字之后的总关灯时长+该数字-1。
记录到第i次操作时亮灯时长记为b[i]。每次操作后开灯时长为：b[i]+m-a[i]-(b[n+1]-b[i])-1，所以遍历一遍维护最大值即可。别忘了可以不操作，此时开灯时长为b[n+1]。

#include 
using namespace std;
const int MAXN = 1e5+5;
int n, m, a[MAXN], b[MAXN];
int main()
{
 scanf("%d%d", &n, &m);
 int f = 1;//开关
 for (int i = 1; i <= n; i++)
 {
  scanf("%d", &a[i]);
  b[i] += b[i-1]+f*(a[i]-a[i-1]);
  f ^= 1;//0->1 or 1->0
 }
 b[n+1] = b[n]+f*(m-a[n]);
 int ans = b[n+1];//不加操作的开灯时长
 for (int i = 1; i <= n; i++)
  ans = max(ans, b[i]+m-a[i]-(b[n+1]-b[i])-1);
 printf("%d\n", ans);
 return 0;
}
/*
3 10
4 6 7
*/