题意
给定一个长度为 \(n\) 的序列。
当连续 \(T\) 天温度都小于 \(0\) 时，则称这 \(T\) 天为一个冰期，冰期来临之前的 \(2T\) 天都被标记为警示状态.
特殊地，如果一个冰期最长，那么它的前 \(3T\) 天会被标记为警示状态。如果有多个冰期最长，选一个。
思路
模拟
- 预处理出每个冰期的长度和起始天数，然后在起始天数的前 \(2T\) 天打上标记（注意不要越界）。
- 对长度进行排序，找出最长天数。在最长天数中比较变成 \(3T\) 后哪一个原先没打上标记现在打上标记的个数最多，找到这个增量。用前缀和数组维护之前被打上标记的个数，以此来找到增量。
- 最后的结果就是原先标记的个数加上这个增量。
代码实现
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt;
#define re register
#define il inline
const int N=1e5+10;
using namespace std;
int a[N];
struct node{
int l,r;
int day;
}icy[N];int cnt;/*icy数组记录冰期左右端点，和持续的时间*/
int ice[N],add[N],l,r,tot;/*ice数据就是标记，add数组是前缀和数组*/
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il bool mysort(node a,node b)
{
if(a.day == b.day) return a.l > b.l;
else return a.day > b.day;/*按天数从大到小排序*/
}
int n,ans;
signed main()
{
n=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int i=1;i<=n;i++)
if(a[i] < 0)
{
icy[++cnt].l=i;
while(a[i]<0 && i<=n) i++; i-=1;/*找冰期的左右端点和持续时间*/
icy[cnt].r=i;
icy[cnt].day=icy[cnt].r-icy[cnt].l+1;
}
for(re int i=1;i<=cnt;i++)
for(re int j=max(1,icy[i].l-icy[i].day*2);j<=icy[i].l-1;j++)/*给每个冰期的前2T天打上标记，注意不要越界*/
ice[j]=1;
for(int i=1;i<=n;i++) add[i]=add[i-1]+ice[i];/*求前缀和数组*/
sort(icy+1,icy+cnt+1,mysort);/*从大到小排序*/
int maxday=icy[1].day,maxcover=0;/*maxcover就是那个增量*/
for(int i=1;i<=cnt;i++)
{
if(icy[i].day < maxday) break;/*不是最长天就可以break了*/
r=icy[i].l-icy[i].day*2-1;/*因为前2T天我们已经打上标记了，我们只需要判断最左边的T的增量就可以了*/
l=icy[i].l-icy[i].day*3;
if(r<=0) continue;/*越界了就continue*/
if(l<=0) l=1;/*l越界了r没有越界，就把l设成1*/
tot=r-l+1;/*计算总共的天数*/
if(maxcover < tot-(add[r]-add[l-1])) maxcover = tot-(add[r]-add[l-1]);/*tot是总天数*/
}/*add[r]-add[l-1]是标记过的天数，一相减，就是变成3T后多出来的个数，即增量*/
printf("%d",maxcover + add[n]); /*增量 + 原先的个数*/
return 0;
}