[数据结构与算法]疫苗小孩＜每日一题＞

题目链接：登录—专业IT笔试面试备考平台_牛客网??????

思路：[牛客][错题]疫苗小孩_wingaso的博客-CSDN博客

这个大佬写的非常好

我就直接照大佬写的给出说明

这里对大佬的代码解释一下

方便大家理解

说明1：

int tT = INT_MIN;//带符号的int对象的最小值，即-2147483648 (在32位编译器上) 

for(int i = 1;i <= n;i++){//从前往后操作，作用：当某天不能打疫苗时，取它前面的能打疫苗的日子
//对可以打针的位置标记，并且A[i]=1的时候标记前面A[i]=0的位置
        if(A[i] == '0') tT = i;
        T[i] = tT;
    }
int tN = INT_MAX;//带符号的int对象的最小值

for(int i = n;i;i--){//从后到前操作，作用：当某天不能打疫苗时，取它后面的能打疫苗的日子
//对可以打针的位置标记，并且A[i]=1的时候标记后面A[i]=0的位置
    if(A[i] == '0') tN = i;
    M[i] = tN;
}

说明2：

T[max(l,1ll)]//防止取的左边打针日期小于1（说明1中向左取值的数组 取天数）

M[max(l,1ll)]//防止取的左边打针日期小于1（说明1中向右取值的数组 取天数）

min(abs(T[max(l,1ll)]-l),abs(M[max(l,1ll)]-l))//取他们距i-k距离最小的天数

T[min(r,(ll)n)]//防止取的右边打针日期大于n（说明1 中 向左取值的数组 取天数）

M[min(r,(ll)n)]//防止取的右边打针日期大于n（说明1 中 向左取值的数组 取天数）
 
min(abs(T[min(r,(ll)n)]-r),abs(M[min(r,(ll)n)]-r))//取他们距i+k距离最小的天数

说明3：?

R+=max(0ll,w-(ll)q*min(abs(T[max(l,1ll)]-l),abs(M[max(l,1ll)]-l)));  // 枚举第T[i-k]和M[i-k](加上最右边的 对手速提升的最大值)

R+=max(0ll,w-(ll)q*min(abs(T[min(r,(ll)n)]-r),abs(M[min(r,(ll)n)]-r))); // 枚举第T[i+k]和M[i+k](加上最左边的 对手速提升最大值)

?代码详解：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int n;
char A[N];
int T[N],M[N];
int main(){
    scanf("%d",&n);
    scanf("%s",A + 1);
    ll k,w,q;
    scanf("%lld%lld%lld",&k,&w,&q);
    int tT = INT_MIN;
    for(int i = 1;i <= n;i++){//对可以打针的位置标记，并且A[i]=1的时候标记前面A[i]=0的位置
        if(A[i] == '0') tT = i;
        T[i] = tT;
    }
    int tN = INT_MAX;
    for(int i = n;i;i--){//对可以打针的位置标记，并且A[i]=1的时候标记后面A[i]=0的位置
        if(A[i] == '0') tN = i;
        M[i] = tN;
    }
    ll ans = 0;
    for(int i = 1;i <= n + 1;i ++){//遍历所有位置
        if(A[i] == '1') continue;
        ll R = 0;
        ll l = i - k,r = i + k;
        R+=max(0ll,w-(ll)q*min(abs(T[max(l,1ll)]-l),abs(M[max(l,1ll)]-l)));  // 枚举第T[i-k]和M[i-k]
        R+=max(0ll,w-(ll)q*min(abs(T[min(r,(ll)n)]-r),abs(M[min(r,(ll)n)]-r))); // 枚举第T[i+k]和M[i+k]
        ans = max(ans,R);每次取最大值
    }
    printf("%lld\n",ans);
    return 0;
}

PS:桃之夭夭，灼灼其华。