自动搬运

查看原文

来自洛谷，原作者为

	Molina 竜は雲の中にいるはずです

搬运于2025-08-24 22:35:47，当前版本为作者最后更新于2023-03-04 14:29:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个长度为 $n$ 的序列，为 $n$ 天每天的温度。

当一天的温度低于 $0$ 时，则为冰冻日。

当连续 $T$ 天都是冰冻日时，则称这 $T$ 天为一个冰期，冰期来临前的 $2T$ 天都被标记为警示状态。

如果其中有一个冰期最长，那么它的前 $3T$ 天会被标记为警示状态。如果有多个冰期最长，则从中选一个冰期，使得处于警示状态的天数最大。

思路

模拟

分别定义了“警示状态”与“冰期”的数组。

进行模拟，如果为冰期则进行标记（见代码），然后标记警示状态，先全部当做 $2T$ 标记，然后找到适合的最大冰期，然后再用 $3T$ 标记。（见代码）

最后用 $ans$ 记录有多少警示状态，便可以开心输出了！完结撒花！

代码来咯~:

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,a[N],znr[N],dt[N],ans=0;//分别定义“警示状态”与“冰期”的数组
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)  cin>>a[i];//输入
	for(int i=1;i<=n;i++){
		if(a[i]<0){
			if(i!=1 && dt[i-1]>=1)  dt[i]=dt[i-1]+1;//如果为一段冰期，则标记出一段冰期
			else dt[i]=1;//如果为冰冻日则进行标记为1；
		}
	} 
	for(int i=n;i>=1;i--)
		if(dt[i]!=0){
			int sum=dt[i];
			for(int j=1;j<=2*sum;j++){
				if(i-sum+1-j>=1)  znr[i-sum+1-j]=1;//标记警示状态
			}
		}
	int zd=dt[n],zdxb=n;
	for(int i=n-1;i>=1;i--){//查找最大冰期
		if(dt[i]>zd){
			zd=dt[i];
			zdxb=i;
		}
		else if(dt[i]==zd){
			int an=0;int bn=0;
			for(int j=1;j<=3*zd;j++)
				if(znr[i-zd+1-j]==0 && i-zd+1-j>=1){
					an++;
				}
			for(int z=1;z<=3*zd;z++)
				if(znr[zdxb-zd+1-z]==0){
					bn++;
				}
			if(an>=bn){//进行比较，找到能使警示状态最多的冰期进行 3T 进行标记
				zdxb=i;
				zd=dt[i];
			}  
		}
	}
	for(int i=1;i<=zd*3;i++)
		znr[zdxb-zd+1-i]=1;
	for(int i=1;i<=n;i++)
		if(znr[i]==1)
			ans++;//记录警示状态
	cout<<ans;
	return 0;
}