CF940D Alena And The Heater 题解

· · 题解

这是本蒟蒻第二十次写的题解，如有错误点请好心指出！

问题简述

这道题我们可以换另一种思路去看待它，就容易理解了：

给你一个正整数 n 和两个长度为 n 的数组 a 和数组 b，其中当 b[i] 等于 1 且不等于 b[i-1] 时，l>max(a[i],a[i-1],a[i-2],a[i-3],a[i-4])；当 b[i] 等于 0 且不等于 b[i-1] 时，r<\min(a[i],a[i-1],a[i-2],a[i-3],a[i-4])，问通过上述条件，l 和 r 分别为多少。

解法综述

按上述直接模拟可能会得出答案，但是需要注意以下 3 点：

  1. 由于数组 b 在输入元素时之间没有空格，不妨将数组 b 定义为字符数组，否则输入 b 数组时还需要经过相对复杂的处理。

  2. 由于 {-10}^9 \leq l \leq r \leq 10^9，为保证后面操作 l 和 r 有效，我们需要在开头初始化 l 为 {-10}^9，r 为 10^9。

  3. 当遍历数组 b 时，要注意在操作时可能要用到 a[i-4]，为保证数组不越界，我们需要使 i 从 b 数组第 5 个元素开始遍历。

代码描述

#include<cstdio>
#include<cstring>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int n,a[100005],l=-1e9,r=1e9;//初始化l和r
char b[100005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%s",b+1);
    int len=strlen(b+1);
    for(int i=5;i<=len;i++)//为保证操作时a[i-4]不越界，i应从5开始遍历
    if(b[i]!=b[i-1])
    {
        if(b[i]=='1') l=max(l,max(a[i],max(a[i-1],max(a[i-2],max(a[i-3],a[i-4])))));
        if(b[i]=='0') r=min(r,min(a[i],min(a[i-1],min(a[i-2],min(a[i-3],a[i-4])))));
    }
    printf("%d %d",l+1,r-1);
    //因为l要大于符合操作的a[i]的最大值且为整数，所以最后输出l+1
    //因为r要小于符合操作的a[i]的最小值且为整数，所以最后输出r-1
    return 0;
}