题目描述

自习室内有一个智能灯。

在 0 时刻，管理员会将打开电闸，并将灯点亮。

在 M 时刻，管理员会直接拉下电闸，此时，如果灯处于点亮状态，则会因为断电而熄灭。

在 0∼M 之间有 n 个不同时刻，不妨用 a1,a2,…,an 表示，其中 0<a1<a2<…<an<M。

在这 n 个时刻中的每个时刻，管理员都会拨动一次智能灯的开关，使灯的状态切换（亮变灭、灭变亮）。

现在，你可以最多额外指定一个时刻（也可以不指定），让管理员在此时刻也拨动开关一次。注意选定的时刻不能与 a1,a2,…,an 相等。

你的目的是让亮灯的总时长尽可能长。

输出这个最大亮灯总时长。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据，第一行包含两个整数 n 和 M。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
输出一个整数，表示最大亮灯总时长。

数据范围
1≤T≤30,
1≤n≤105,
2≤M≤109,
0<a1<a2<…<an<M。
同一测试点内所有 n 的和不超过 105。

样例

输入样例：
3
3 10
4 6 7
2 12
1 10
2 7
3 4
输出样例：
8
9
6

算法1

(贪心+前缀和) $O(n)$

1.前缀和

2.找规律，找位置关系
（1）在某个区间加点时。这个区间的长度要大于1
（2）加点的区间左侧，前缀和不变
中间总能想办法，得到zone - 1
右侧的区间，前缀的奇偶性发生翻转

时间复杂度

参考文献

python3 代码

T = int(input())
for _ in range(T):
    n, M = map(int, input().split())
    a = [int(x) for x in input().split()]
    a = [0] + a
    a.append(M)
    n += 2

    #---- 区间
    b = []
    for i in range(1, n):
        b.append(a[i] - a[i - 1])
    bn = n - 1

    #---- 后缀和比前缀和好用一点
    presum_odd = [0 for _ in range(bn + 1)] #奇偶性从0开始计
    presum_even = [0 for _ in range(bn + 1)]
    for i in range(bn):
        zone = b[i]
        presum_even[i+1] = presum_even[i]
        presum_odd[i+1] = presum_odd[i]
        if i % 2 == 1:
            presum_odd[i+1] += zone
        else:
            presum_even[i+1] += zone

    #---- 假设不动
    res = presum_even[bn]

    #---- 若动
    for i in range(bn):
        zone = b[i]
        if zone == 1:
            continue
        L = presum_even[i]
        mid = zone - 1
        R = presum_odd[bn] - presum_odd[i + 1]
        res = max(res, L + mid + R)

    # print(presum_odd)
    # print(presum_even)

    print(res)

C++ 代码

# include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;    cin >> T;
    while (T --)
    {
        int n;    cin >> n;
        int M;    cin >> M;
        int a[n + 2];
        int an = n + 2;
        a[0] = 0;
        for (int i = 1; i < n + 1; i ++)    
            cin >> a[i];
        a[n + 1] = M;

        int b[an - 1];
        for (int i = 1; i < an; i ++)
            b[i-1] = a[i] - a[i-1];

        int bn = an - 1;
        int presum_even[bn + 1];    //前缀和  
        memset(presum_even, 0, sizeof(presum_even));
        int presum_odd[bn + 1];     
        memset(presum_odd, 0, sizeof(presum_odd));

        for (int i = 0; i < bn; i ++)
        {
            int zone = b[i];
            presum_even[i+1] = presum_even[i];
            presum_odd[i+1] = presum_odd[i];
            if (i % 2 == 0)
            {
                presum_even[i+1] += zone;   //奇偶性从0开始计
            }
            else
            {
                presum_odd[i+1] += zone;
            }
        }

        //---- 假设不动
        int res = presum_even[bn];

        //---- 动了
        for (int i = 0; i < bn; i ++)
        {
            int zone = b[i];
            if (zone == 1)
                continue;
            int L = presum_even[i];
            int mid = zone - 1;
            int R = presum_odd[bn] - presum_odd[i+1];
            res = max(res, L + mid + R);
        }

        cout << res << endl;
    }

    return 0;
}

java 代码

import java.util.* ;

public class Main
{
    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0)
        {
            int n = scan.nextInt();
            int M = scan.nextInt();

            int [] a = new int [n + 2];
            int an = n + 2;
            a[0] = 0;
            for (int i = 1; i < n + 1; i ++)
                a[i] = scan.nextInt();
            a[n+1] = M;

            int [] b = new int [an - 1];
            int bn = an - 1;
            for (int i = 1; i < an; i ++)
                b[i-1] = a[i] - a[i-1];

            int [] presum_even = new int [bn + 1];  //奇偶性从0开始计，虚指
            int [] presum_odd = new int [bn + 1];
            for (int i = 0; i < bn; i ++)
            {
                int zone = b[i];
                presum_even[i+1] = presum_even[i];
                presum_odd[i+1] = presum_odd[i];
                if (i % 2 == 0)
                {
                    presum_even[i+1] += zone;
                }
                else
                {
                    presum_odd[i+1] += zone;
                }
            }

            //---- 若是不动
            int res = presum_even[bn];

            //---- 若是动
            for (int i = 0; i < bn; i ++)
            {
                int zone = b[i];
                if (zone == 1)
                    continue;

                int L = presum_even[i];
                int mid = zone - 1;
                int R = presum_odd[bn] - presum_odd[i + 1];
                res = Math.max(res, L + mid + R);
            }

            System.out.println(res);
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla