题目描述

一组灯，时刻0时全部打开，时刻m时全部关闭。
0到m之间还有n个时刻来开关灯，原先灭的灯会亮，亮的灯会灭。
你可以在0到m之间选择一个时刻（不能与n个时刻中的任意时刻相等）来开关灯，改变灯的状态。
问灯亮的最长时间。

题解

贪心+前缀/后缀和数组
将题目转化为长度为m的线段，左端点为0，右端点为m。中间n个时刻点，把线段分割成n+1个区间。
设a[i]为第i个时刻。
假设在第i和第i+1个时刻(i和i+1均为数组下标)之间的时刻开关灯，那么灯亮的时间为
i之前的奇区间和i+1之后的偶区间和i+1与i之间的亮灯时间。
贪心可知i+1与i之间的亮灯时间最大为a[i+1]-a[i]-1。
我们只需要枚举在哪个区间开关灯即可，枚举i,答案由
i之前的奇区间和i+1之后的偶区间和a[i+1]-a[i]-1三部分组成。
开两个前缀或后缀和数组，记录偶区间和奇区间的和，实现O(n)更新答案。

时间复杂度

O(N)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 100002

int T;
int a[N];
int s1[N],s2[N];

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[0]=0;a[++n]=m;
        for(int i=0;i<=n;i++)
        {
            s1[i]=s2[i]=0;
        }
        for(int i=n-1;i>=0;i--) //后缀数组
        {
            s1[i]=s1[i+1]; //s1奇数区间
            s2[i]=s2[i+1]; //s2偶数区间
            if(i%2) s2[i]+=(a[i+1]-a[i]);
            else s1[i]+=(a[i+1]-a[i]);
        }
        int res=0;
        for(int i=0;i<n;i++)
        {
            if((a[i+1]-a[i])==1) continue;
            res=max(res,s1[0]-s1[i]+s2[i+1]+a[i+1]-a[i]-1);//i之前的奇数区间和（i+1）之后的偶数区间+当前区间长度-1
        //   cout<<i<<"---"<<s1[0]-s1[i]+s2[i+1]+a[i+1]-a[i]-1<<endl;
        }
        res=max(res,s1[0]); //也可以不开关 开关
       cout<<res<<endl;
    }
    return 0;
}