参考题解视频链接:Google Kickstart题目讲解
题目描述
题意是求最大的连续排在一起的糖果的甜度总和,也就是最大连续区间和。
但是,题目给这个区间和加上了两个条件:
- 区间内奇数个数不能超过
O
个 - 区间和不能超过
D
糖果数组是用给定的参数生成的。
算法
(前缀和+滑动窗口+二分) $O(n log(n))$
对题目这两个条件,我们分别考虑。
首先处理区间内奇数个数:
对于O
个奇数的限制,我们可以找到连续的O+1
个奇数,第一个奇数之后的那个数一直到第O+1
个奇数的这个区间就是符合条件的区间。
比如这个序列:1,2,3,4,5,6,7
, 当 O
为 1
时,先找到1
和3
这两个奇数,他们划分的区间就为[2,3]
。
区间和不能超过D:
对于区间求和,我们通常可以用前缀和(Prefix sum)来做,对前缀和不熟悉的同学可以去查看《算法竞赛进阶指南》打卡活动中的激光炸弹、IncDec序列和最高的牛这三题及相关的题解。前缀和保证每次的区间求和操作是O(1) 的时间复杂度。
对于任意一个满足条件的区间,我们要从中找到两个端点i, j (i > j)
,使得 prefix_sum[i] - prefix_sum[j - 1] <= D
且最大,即 j
满足:
prefix_sum[j - 1]
是最小的满足prefix_sum[j - 1] >= prefix_sum[i] - D
的那个。这个形式很容易看出就是有序序列中的 lower bound 查找。因此,为了避免一次次遍历,我们将prifix_sum
保存为一个有序的序列。在C++中,可以用multiset
这个数据结构来做,因为在计算的过程中,区间是变化的,需要在有序的序列中进行插入和删除操作;同时,前缀和并不唯一,一个区间内可以有多个相同的前缀和,所以用的是multiset
而不是 set
。
时间复杂度
由于在遍历的时候,计算区间的末尾点和起始点是单调的,每个点至多被计算一次。同时,每次计算需要在一个有序的序列中查找,所以最终的复杂度是$O(nlog(n))$。
C++ 代码
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int main() {
long long T, n, o, d;
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> n >> o >> d;
long long x1, x2, a, b, c, m, l;
cin >> x1 >> x2 >> a >> b >> c >> m >> l;
vector<long long> nums(n + 1, 0), sum(n + 1, 0);
nums[1] = x1, nums[2] = x2;
for (int i = 3; i <= n; ++i) {
nums[i] = (a*nums[i - 1] + b*nums[i - 2] + c) % m;
}
for (int i = 1; i <= n; ++i) {
nums[i] += l;
}
for (int i = 1; i <= n; ++i)
sum[i] += sum[i - 1] + nums[i]; // 求前缀和
multiset<long long> ordered_sum;
long long beg = 0, end = 0, cnt = 0;
long long ans = -1e18;
while(end <= n) {
if (nums[end] & 1) {
++cnt; // 当前糖是奇数
}
// 奇数糖溢出时,移动beg位置直至不溢出
if (cnt > o) {
ordered_sum.erase(ordered_sum.find(sum[beg++]));
while ((beg <= end && nums[beg] & 1) == 0) {
ordered_sum.erase(ordered_sum.find(sum[beg++]));
}
--cnt;
}
auto it = ordered_sum.lower_bound(sum[end] - d);
if (it != ordered_sum.end()) {
ans = max(ans, sum[end] - *it);
}
ordered_sum.insert(sum[end++]);
}
if (ans == -1e18)
cout << "Case #" << t << ": IMPOSSIBLE" << endl;
else
cout << "Case #" << t << ": " << ans << endl;
}
return 0;
}
几个需要注意的点
- 用
multiset::lower_bound
而不是std::lower_bound
。这是由于std::lower_bound
仅仅在输入的是random_access_iterator
的时候才保证$O(log(n))$的时间复杂度。而set
的迭代器仅仅是bidirectional_iterator
。 - 用
ordered_sum.erase(ordered_sum.find(sum[beg++]))
而不是ordered_sum.erase(sum[beg++])
,前者是删一个,后者是全删了。
参考链接
[1] http://www.cplusplus.com/reference/algorithm/lower_bound/
[2] http://www.cplusplus.com/reference/set/multiset/lower_bound/
这个双指针里面的循环 逻辑写的实在是太妙了!!学习了