要求使得区间和小于 \(k\) 的子区间长度，显然可以二分处理。二分区间长度，枚举区间左端点，check 两项内容：区间是否合法（符合 \(h_i \mod h_{i+1}=0\) ），区间和是否小于 \(k\)。对于当前区间长度，只要有一个区间满足条件，即返回真。
区间和可以通过前缀和 \(O(1)\) 的计算，而区间的合法性则可以记录每个 \(i\) 到自身所属的最大合法段右端点的距离来判断，总时间复杂度 \(O(n\log n)\)。
下面是 AC 代码：
inline bool check(vector<int>& a, vector<int>& len, int n, int k, int x) {
for (int i = 1; i <= n; i++) {
if (i + x - 1 <= i + len[i] && a[i + x - 1] - a[i - 1] <= k) {
return true;
}
}
return false;
}
void solve() {
//输入部分省略
vector<int> len(n + 1);
for (int i = n - 1; i >= 1; i--) {
if (h[i] % h[i + 1] == 0) {
len[i] = len[i + 1] + 1; //i 到自身最大合法段右端点的距离
}
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1; //都试一下，RE 就换另一个
if (check(a, len, n, k, mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l << endl;
}
近期做题的几点教训：
- 明确变量的含义，到底是“到末尾的距离”还是“区间的长度”，加 1 减 1 的失误往往会导致惨痛后果；
- 二分 while 循环的条件始终是 \(l<r\)；\(l,r\) 改变必须保证答案在答案区间内；\(mid\) 是 \((l+r)/2\) 还是 \((l+r+1)/2\) 可以自己试一试；
- 明确 \(l,r\) 的初始值，也就是答案的可能范围，过小则找不到答案，过大容易造成溢出；这个问题值得花时间认真计算一下，不要想当然；
- 数字相乘一定想一下是否会爆 int 或 long long！