Codeforces 1000B Light It Up
题目大意:有一盏灯，在0时刻亮起，M时刻关闭。在一些时刻有一些开关可以改变灯的状态(开-->关,关-->开)。给你一个机会再0~m任何一个时刻(不与a[i]相同)加一个开关,求灯亮着的最大时间。
显然应该把这个开关安排在任何一个a[i]的相邻位置(左边或右边),这样浪费的时间会最少。然而无论在左边还是右边,两个情况都是同一个道理,所以我们只需要考虑放在a[i]左边相邻的一种情况。
这题的妙处就是:无论在哪添加这个开关，每个开关对于改变灯的状态都会改变。
Eg:如果这个开关原本会把灯关掉，那么添加开关后它会让灯亮。
我们处理一个b[i]前缀和数组,表示a[i]时刻前灯亮的时间;c[i]前缀和数组表示a[i]时刻后灯关着的时间;
那么当把灯放在a[i]-1时刻时,只会影响a[i]前面灯亮着的时间少了1,而后面亮着的时间再此时由未添加开关时的b[n]-b[i]变成了c[n]-c[i] (因为a[i]后每个开关对于改变灯的状态改变,关--开);
m可以看做一个时刻算到b[n+1],c[n+1]中，所以在a[i]-1处添加开关的贡献是b[i]-1+c[n+1]-c[i],扫一遍维护最大值。
由于可以不加开关,还要将答案与不加开关的时间比较。
C++代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%d ",a)
using namespace std;
int n,m;
int a[100050],b[100050],c[100050];
int now,ans,sum;
int read()
{
int s=0,t=1; char c;
while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
return s*t;
}
int main()
{
n=read(); m=read(); ans=-2333333;
for (int i=1;i<=n;i++){
a[i]=read(); b[i]=b[i-1]; c[i]=c[i-1];
if (i&1) b[i]+=a[i]-a[i-1],sum+=a[i]-a[i-1];
else c[i]+=a[i]-a[i-1];
}
if (n&1) b[n+1]=b[n],c[n+1]=c[n]+m-a[n];
else b[n+1]=b[n]+m-a[n],c[n+1]=c[n],sum+=m-a[n];
for (int i=1;i<=n+1;i++)
now=b[i]+c[n+1]-c[i]-1,ans=max(now,ans);
ans=max(ans,sum);
out(ans);
return 0;
}
