AcWing 3774. 亮灯时长
原题链接
中等
作者:
思念是一种病
,
2021-08-20 17:10:47
,
所有人可见
,
阅读 173
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int T,n,m;
const int N = 1e5+10;
int a[N];// 存下所有的区间坐标
int s1[N],s2[N];
int main()
{
cin>>T;
while(T --)
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[++n]=m;
//读入这n+2个节点坐标
s1[0]=s2[0]=0;
/*
这个下标 i 指的是 第几个区间 我们已经不在乎 这个区间的左右端点了
一共有多少区间呢?
一共有 n+2个端点 便有n+1个区间
但是我们的 n自增了一次 也就是 n个区间
第i个区间的 左右端点呢?
a[i-1] a[i]
*/
for(int i=1;i<=n;i++)
{
s1[i]=s1[i-1];
s2[i]=s2[i-1];
if(i%2==1) s1[i]=s1[i-1]+(a[i]-a[i-1]);
else s2[i]=s2[i-1]+(a[i]-a[i-1]);
}
int res=s1[n]; //不枚举的话 答案就是 最后一个区间的右端点的奇数区间的前缀和
//处理好 奇偶区间的前缀和
for(int i=1;i<=n;i++)
{
int t=a[i]-a[i-1];
//枚举这个 区间的长度 要是长度就是1 说明无缝可插
if(t==1) continue;
else
{
res=max(res,s1[i-1]+s2[n]-s2[i]+t-1);
}
}
printf("%d\n",res);
}
}