题解 - 【挑战题】发射站 - 核OJ_核桃编程

2
tusichang~ MOD @ 2024-4-2 17:11:05
这道题其实查询的是h数组中的每一个 $[i-k,i+k]$ 区间的最大值，并把v[i]赋值给它. $\\$ 所以定义 $sum$ 数组表示每个点接收的能量值大小。 $\\$ 由于最大的情况可能会考虑到第 $n$ 个发射站需要查询 $[n-k,n+k]$ 中的最大值，所以我们可以枚举区间的右边界 $i$ 从 $1$ 循环到 $n+k$ ，这是合理的，因为当 $j>n$ 时， $h[j]=0$ ，对我们选取区间最大值，不会有任何影响。 $\\$ 考虑右边界 $i$ 入队时，第一步去头，此时左边界是 $i-2*k$ .所以只有当 $i-2*k> q[head]$ 时，才让 $head++$ $\\$ 接着维护队列单调性，求的是最大值，所以维护一个单调递减队列。 $\\$ 然后让新元素 $i$ 入队。 $\\$ 最后只有个当 $i>k+1$ 时才是合法区间，此时区间中间值 $v[i-k]$ 加到 $sum[q[head]]$ 中. $\\$ 最后遍历 $sum$ 数组，找到最大值~
参考代码

#include<iostream> using namespace std; int n, head = 1, tail,k; long long h[2000001],v[2000001], sum[2000001], q[2000001],ans=-1000000; int main() { cin >> n >> k; for ( int i = 1; i <= n; i ++) cin >> h[i] >> v[i]; for (int i = 1; i <= n+k ; i ++) { if (head <= tail && i-2*k> q[head]) head++; while (head <= tail && h[i] >= h[q[tail]]) tail--; q[++tail] = i; if(i>=k+1) sum[q[head]]+=v[i-k]; } for(int i=1;i<=n;i++) { if(ans<sum[i]) ans=sum[i]; //cout<<sum[i]<<endl; } cout<<ans; return 0; }

ID: 701
时间: 1000ms
内存: 256MiB
难度: 4
标签: (无)
递交数: 58
已通过: 29
上传者: tusichang~