AcWing 3774. 亮灯时长

原题链接

题解

题目描述

自习室内有一个智能灯。
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≤10^5,
2≤M≤10^9,
0<a1<a2<…<an<M。
同一测试点内所有 n 的和不超过 10^5。


分析

后/前缀和 贪心 O(n)

题目要求:可以选择加入一个不同时刻,使灯的状态多切换一次,让亮灯的时间最长。
注意到加入一个时刻后,此时刻后面区间的亮/灭状态全都变反。

用a0, a1, ... , an, an+1表示各时刻,其中a0=0, an+1=M
注意到对于[ai, aj]区间:
i为偶数,j为奇数时,灯亮
i为奇数,j为偶数时,灯灭

可以用一个后缀和s[i]表示从ai时刻开始到M时刻的亮/灭总时长,若i为偶数,表示亮灯总时长,奇数表示灭灯总时长。
则s[0]表示原始的亮灯总时长。

显然,如果加入一个时刻,要么在一个亮灯的区间加入,要么在一个灭灯的区间加入。
一旦选择一个区间[ai, aj]加入一个时刻x,这个区间后面(取反)和前面(不变)亮灯的时长是确定的,只需要考虑x如何插入的问题:
[ai, aj]是亮灯的区间,则[ai, x]灯亮,[x, aj]灯灭,显然要aj-x最小,为1,x-ai最大,为aj-ai-1
[ai, aj]是灭灯的区间,则[ai, x]灯灭,[x, aj]灯亮,显然要x-ai最小,为1,aj-x最大,为aj-ai-1

初始化为s[0],枚举每一个区间插入,计算最大值即可。时间复杂度O(n)

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int t, n, m, a[N];
ll s[N], on;

void init() {
    a[n+1] = m;
    s[n+2]=s[n+1]=0;
}

int main() {
    scanf("%d", &t);
    a[0] = 0;
    while(t --) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        init();
        for(int i = n; i >= 0; i --)
            s[i] = s[i+2] + a[i+1]-a[i];
            
        on = s[0];
        
        for(int i = 0; i <= n; i ++) {
            if(i&1) on = max(on, a[i+1]-a[i]-1 + s[0]-s[i+1] + s[i+2]);
            else on = max(on, -1 + s[0]-s[i+2] + s[i+1]);
        }
        printf("%lld\n", on);
        
    }
    return 0;
}
上一篇:Codeforces Round #735 (Div. 2) 题解


下一篇:算法分析与设计实践作业8