[数据结构与算法]牛客寒假算法基础集训营5-A.疫苗小孩

标签：二分

思路

看到数据范围，显然不能三针都枚举，但注意到疫苗一共只能接种三针，且第二第三针才会对手速产生影响，考虑是否可以通过枚举一针，进而确定剩余两针的位置，由于三针疫苗是有先后顺序的，所以显然枚举第二针然后往前找第一针和往后找第三针会比较好操作，将能够打疫苗的日子存储到a中，它是从小到大排列的，所以可以使用二分

那么就是枚举第二针，第一针和第三针应该找距离相差k天最近的位置，注意这里使用的是lower_bound，它找到的是第一个大于等于目标的位置，所以返回的位置可能不是恰好相差k天的位置，如果是这种情况就需要和另一侧比较一下谁更接近相差k天的位置，还有可能会返回当前位置，显然不能两针在一天打，那么就应该前移一位

代码实现

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
const int N=1e6+5;
int n;
string s;
long long k,w,q;
int a[N];
int main(){
    cin >> n;
    cin >> s;
    cin >> k >> w >> q;
    int cnt = 0;
    for(int i = 0; i < n; i++){
    	if(s[i] == '0') a[++cnt] = i+1;
	} 
	int pre = 0, nxt = 0;
	long long ans = 0; 
	a[0] = -1e9;       //将数组两侧初始化，防止找到外面 
	a[cnt+1] = 1e9;
	for(int i = 1; i < cnt; i++){
		long long m1 = 0, m2 = 0;     
		pre = lower_bound(a+1, a+i-1, a[i] - k)-a;
		nxt = lower_bound(a+i+1, a+cnt+1, a[i] + k)-a;
		if(pre == i || abs(k-a[i]+a[pre]) > abs(k-a[i]+a[pre-1])) pre--;
		if(nxt != i+1 && abs(k-a[nxt]+a[i]) > abs(k-a[nxt-1]+a[i])) nxt--;
		m1 = max(m1, w-abs(k-(a[i]-a[pre]))*q);//由于m1,m2初始化为0，所以在手速提升为负数时会取较大值0 
		m2 = max(m2, w-abs(k-(a[nxt]-a[i]))*q);//这样就保证了答案最大 
		ans = max(ans, m1+m2);
	}
	cout << ans;
	return 0;
}