题目描述
0刻开闸,亮灯
接下来给n个时刻,在这n个时刻到达时,按一下开关
M刻拉闸,灭灯
现在,你可以偷偷的再在0~M之间私自按一下开关(也可以不按)
但是你不可以在这n个时刻中同时按开关
所以,你要最多可以做到多长的总亮灯时间?
思考
这道题可以说是初级知识的集大成者,需要用到:
1,贪心
2,前缀和 后缀合
3,离散化
4,枚举
都不是什么特别尴尬的知识点,重点在巧妙的结合
首先,我们从最开始来思考
:
理论上,我们有0~M个时刻来选择,M的范围是10^9
啥也不说了,直接超时,剪枝都不带机会的
但是,好好想想,我们确实每个时刻都要考虑吗?
不是的!
设O位于n1和n2之间
此时灯按了一下,是亮着的
如果我们这个时候按一下,那么现在灯会变暗
而等下一个时刻到的时候,灯又会变亮(而原来统计的时候,这个时候是灭灯)
也就是说:
n2时刻后,原本统计的灭灯时间为开灯时间!
而原本统计的开灯时间为灭灯时间!
n1时刻前的不变
而O,在n1和n2之间,只有尽量靠前!
也就是,在n1和n2之间,O = n1+1 就会达到在这个区间按的最佳效果
当然了,要记得特判!
而另一种情况,其实也是一样的
如果这个时候灯是亮的,那么就要尽晚点击,让亮灯尽量延长
按找上面的说法,其实我们就只要枚举n个时刻就可以啦
算出亮灯时长,取最大的一个
但是!问题又来了!
我们怎么算亮灯时长呢?
那不是对于每一个点,我们又要跑一次O(n)?
其实不用!
我们跑一边前缀和,跑一边后缀和就可以啦!
跑前缀和,记录i时刻前的亮灯时长
跑后缀和,记录i时刻后的灭灯时长
然后,对于时刻n[i]和n[i+1]之间的方案,亮灯时长为:sumq[i]+(n[i+1]-n[i]-1)+sumh[i+1]
只要O(1)算出来
而整个算法也只要O(n)!
Over~
(大杂烩算法) $O(n)$
记得要特判!!!
C++ 代码
#include <iostream>
using namespace std;
int T,n,M;
int a[100010],sumq[100010],sumh[100010],ans;
int main(){
cin >> T;
while(T--){
cin >> n >> M;
a[0]=0;sumq[0]=0;sumh[n+1]=0;ans=0;
for(int i=1;i<=n;i++){
cin >> a[i];
if(i%2==1){
sumq[i]=sumq[i-1]+a[i]-a[i-1];
}else{
sumq[i]=sumq[i-1];
}
}
a[n+1]=M;
if(n%2==0){
sumq[n+1]=sumq[n]+a[n+1]-a[n];
}else{
sumq[n+1]=sumq[n];
}
for(int i=n;i>=0;i--){
if(i%2==1){
sumh[i]=sumh[i+1]+a[i+1]-a[i];
}else{
sumh[i]=sumh[i+1];
}
}
ans=sumq[n+1];
for(int i=0;i<=n;i++){
if(a[i+1]-a[i]>1){
int sum=sumq[i]+sumh[i+1]+(a[i+1]-a[i]-1);
ans=max(sum,ans);
}
}
cout << ans << endl;
}
return 0;
}
噢,你是一个前缀一个后缀 qwq
两个前缀和就行了吧,对于每个亮暗区间,我们的最优解肯定是对左边界进行一次开关变化,所以我们只需要分别求出亮暗区间的前缀和
对耶!确实省了时间和空间!