P1714. 切蛋糕

发表于 分类于 阅读次数： Waline： 本文字数： 241 阅读时长 ≈ 1 分钟

考点

  • 单调队列
  • 前缀和

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 50;
int n, m, pre[maxn];
int head, tail, q[maxn];

int main() {
  cin >> n >> m;
  int ans = 0xc0c0c0c0;
  for (int i = 1; i <= n; ++i) cin >> pre[i], pre[i] += pre[i - 1];
  for (int i = 0; i < n; ++i) {
    while (head < tail && q[head] - 1 + m < i) ++head;
    while (head < tail && pre[q[tail - 1]] > pre[i]) --tail;
    q[tail++] = i;
    ans = max(ans, pre[i + 1] - pre[q[head]]);
  }
  cout << ans;
  return 0;
}

思路

一开始的想法肯定是前缀和，然后左端点l和右端点r随便选....但显然会TLE。

考虑到前缀和的公式pre[r] - pre[l - 1]，

相同的pre[r]时，显然pre[l - 1]最小时就能得到m区间长度内的极大值。

推导得到l - 1的区间范围： \[ \\ \left( l-1 \right) \in \left[ r-m,r-1 \right] \begin{cases} r-l+1\leqslant m\Longrightarrow r-m\leqslant l-1\\ l-1\leqslant r-1\\ \end{cases} \] 所以用单调队列保存该区间内的极小值，用来更新r即可