暴力做法$O(n^2)$:枚举区间，求区间平均值是否大于$k$
正解：
设$f(i)=min(j)(1 \leq j \leq i$且$sum_i-sum_{j-1} \geq 0)$
如果存在$k < j, sum_k < sum_j$，那么$j$无用，把无用的$j$去掉，单调栈维护即可。
然后再判区间和是否大于0(倒序扫$i$,算每个$f(i)$)，然后更新答案即可
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define db double
#define FN2 "blocks"
LL n, m;
LL a[1000000 + 5], sum[1000000 + 5], top, st[1000000 + 5];
void clean() {
for (LL i = 0; i <= 1000000 + 1; i++) a[i] = sum[i] = 0;
}
LL work(LL k) {
top = 1;//see the reson below
LL ret = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i] - k;
if (!top || sum[st[top]] > sum[i]) st[++top] = i;
}
for (int i = n; i >= 1; i--) {
while (top && sum[st[top]] <= sum[i]) top--;
ret = max(ret, i - st[top + 1]);
//if not to set top to 1, perhaps get st[1] when top became 0 instead of 0
}
return ret;
}
void solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (LL i = 1; i <= m; i++) {
LL opt ; scanf("%lld", &opt);
printf("%lld ", work(opt));
}
puts("");
}
int main() {
freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
scanf("%lld%lld", &n, &m), solve();
fclose(stdin), fclose(stdout);
return 0;
}
题目描述
给定一个长度为N的正整数序列A,你可以进行如下操作:
每次选择一个大于K的正整数a[i]，将a[i]减去1,选择a[i- 1]或a[i + 1]中的一个加上1
请问:经过若干次操作之后，最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于K
本题有M组询问，每次询问一个数K,你需要分别回答
Input
第一行两个正整数，表示N,M,含义如题所示。
第二行N个正整数，表示a序列。
第三行M个正整数表示M次询问的K
𝟏𝟎 𝟓
𝟏 𝟕 𝟗 𝟗 𝟓 𝟗 𝟑 𝟒 𝟓 𝟖
𝟓 𝟕 𝟐𝟎 𝟗 𝟏
Output
一行M个整数，表示每次询问的答案，用空格隔开。
𝟏𝟎 𝟔 𝟎 𝟐 𝟏𝟎
对于40%的数据，有$1\leq Ai \leq 10^9, 1 \leq K \leq 10^9, 1 \leq m \leq 50, 1 \leq n \leq 10000$
对于100%的数据，有$1\leq Ai \leq 10^9, 1 \leq K \leq 10^9, 1 \leq m \leq 50, 1 \leq n \leq 1000000$
