zzs 和 zzy 正在被寒假作业折磨,然而他们有答案可以抄啊。
他们共有 n n n 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 a i a_i ai?,表示抄这个作业所要花的精力。
zzs 现在想要知道,有多少组连续的寒假作业的疲劳值的平均值不小于 k k k?
简单地说,给定一个长度为 n n n 的正整数序列 { a i } \{a_i\} {ai?},求出有多少个连续子序列的平均值不小于 k k k。
第一行是两个整数,分别表示序列长度 n n n 和给定的参数 k k k。
第二行有 n n n 个整数,第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai?。
输出一行一个整数表示答案。
3 2
1
2
3
4
共有 6 6 6 个连续的子序列,分别是 ( 1 ) (1) (1)、 ( 2 ) (2) (2)、 ( 3 ) (3) (3)、 ( 1 , 2 ) (1,2) (1,2)、 ( 2 , 3 ) (2,3) (2,3)、 ( 1 , 2 , 3 ) (1,2,3) (1,2,3),平均值分别为 1 1 1、 2 2 2、 3 3 3、 1.5 1.5 1.5、 2.5 2.5 2.5、 2 2 2,其中平均值不小于 2 2 2 的共有 4 4 4 个。
以上来自洛谷 以上来自洛谷 以上来自洛谷
题目看不懂?确实题面可以转化为:求平均值大于等于k的区间个数。是不是想用 C D Q CDQ CDQ 了?我偏不用。
枚举每个区间的右端点,枚举相应的区间。时间复杂度 O ( n 2 ) O(n^2) O(n2)。
对于平均值的处理,可以把
a
i
?
k
a_i-k
ai??k,这样问题就转换为求出区间和大于等于0的区间个数
枚举右端点之后,考虑怎么快速求出左边区间和大于等于
0
0
0 的个数。
定义
t
o
t
tot
tot 表示当前以
i
i
i 为右端点的前缀和,用一个vector<int> sum
维护当前右端点对应的所有左端点加
t
o
t
tot
tot 表示某段区间和。这样每次只要求出
s
u
m
+
t
o
t
≥
0
sum+tot\ge 0
sum+tot≥0 的个数,很容易想到二分,不可以手打,但有函数可以直接用。用lower__bound
与insert
保证插入后vector
有序。考虑插入对于当前位置
j
j
j,
j
j
j 到
i
i
i 的区间和,表示为
S
u
m
[
i
]
?
S
u
m
[
j
?
1
]
Sum[i]-Sum[j-1]
Sum[i]?Sum[j?1]。而
s
u
m
j
?
1
sum_{j-1}
sumj?1? 就是当前枚举到j还没有加上
a
j
a_j
aj? 的
t
o
t
tot
tot。时间复杂度
O
(
n
×
n
)
O(n\times \sqrt n)
O(n×n?),这不就过了吗。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 4e5 + 5;
int n, k, a[Maxn];
vector<int> sum;
int tot;
int ans;
inline void work() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] -= k;
}
int tmp;
for (int i = 1; i <= n; i++) {
sum.insert(lower_bound(sum.begin(), sum.end(), -tot), -tot);
tot += a[i];
tmp = sum.end() - lower_bound(sum.begin(), sum.end(), -tot);
ans += tmp;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
work();
return 0;
}
//CDQ?
什么?你还想写 C D Q CDQ CDQ?