P8081 [COCI2011-2012#4] ZIMA 题解

Molina · 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;
}