CF1873F Money Trees

这篇博客记录了解决题目 CF1873F Money Trees 的思路和代码，其中使用双指针和二分答案的方法来找到满足条件的最长线段长度。

题目大意

有 $n$ 棵树，每棵树高 $h_i$，有 $a_i$ 个果子。

你可以选一对 $l$ 和 $r$，使得 $h_{i+1}\mid h_i\space(l\le i<r)$ 且 $a_l+a_{l+1}+\dots +a_r\le k$。

求 $r-l+1$ 的最大值。

思路

先 $O(N)$ 的找出所有符合整除条件的长线段，然后在每个长线段中找一条最长的和不超过 $k$ 的线段。这一操作可以用二分答案或双指针来实现。最开始使用贪心，贪心地去删除左右两边一个更大的值，但是这样贪心是错误的。

注意到对于每个左端点 $l$，它的最大 $r$ 是不降的，符合双指针的使用场景，因此也可以直接在遍历所有树的时候用双指针处理。

代码

int n, k, a[maxN + 5], h[maxN + 5], res, sum[maxN + 5];
int check(int l, int r, int len) {
    int cnt = (r - l + 1) - len + 1;
    rep(i, 0, cnt - 1) {
        int st = l + i, ed = l + i + len - 1;
        if (sum[ed] - sum[st - 1] <= k)
            return 1;
    }
    return 0;
}
int calc(int l, int r) { //[l,r)
    int sum = 0;
    r--;
    int left = 0, right = r - l + 1, res = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(l, r, mid)) {
            res = mid, left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}
void solve() {
    res = 0;
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> h[i];
    rep(i, 1, n) sum[i] = sum[i - 1] + a[i];
    int l = 1, r;
    for (r = 2; r <= n; r++) {
        if (h[r - 1] % h[r] != 0) {
            res = max(res, calc(l, r));
            l = r;
        }
    }
    res = max(res, calc(l, r));
    cout << res << endl;
}