nowcoder多校9-Cutting Bamboos(二分+主席树)

题目链接:nowcoder多校9-Cutting Bamboos

题意:

给n棵竹子,q个询问,每次询问给定(l,r,x,y),区间[l,r]内的所有竹子要求砍y刀,每刀砍下来的竹子的长度要相等,问第x刀砍在什么高度。

题解:

主席树+二分。

主席树维护区间内的数在某个区间内的个数和该区间内的数的和。

对于每次询问,我们可以转化为砍了x刀后,剩下的竹子的总长度,然后二分dix刀砍在哪里,高于刀的竹子的长度按二分出的答案处理,低于刀高度的用主席树维护和。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 10;
const int inf = 1e9 + 9;
int n, m;
double S[MAXN];
LL sum[MAXN << 5], sz[MAXN << 5];
int h[MAXN];
int tot = 0, cnt;
int Tree[MAXN << 5], ls[MAXN << 5], rs[MAXN << 5];
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sz[rt] = sz[las] + 1;
    sum[rt] = sum[las] + val * 1LL;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
double t1, t2;
void query(int L, int R, int l, int r, int lt, int rt)
{
    if (L <= l && r <= R)
    {
        t1 += (sum[rt] - sum[lt]) * 1.0;
        t2 += (sz[rt] - sz[lt]) * 1.0;
        return;
    }
    int mid = (l + r) / 2;
    if (L <= mid)
        query(L, R, l, mid, ls[lt], ls[rt]);
    if (R > mid)
        query(L, R, mid + 1, r, rs[lt], rs[rt]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &h[i]);
        S[i] = S[i - 1] + h[i];
        update(Tree[i - 1], h[i], 1, 100000, Tree[i]);
    }
    while (m--)
    {
        int l, r;
        double x, y;
        scanf("%d%d%lf%lf", &l, &r, &x, &y);
        double t = (S[r] - S[l - 1]) / y * (y - x);
        double L = 0.0, R = 1e5 * 1.0;
        while (R - L > 1e-6)
        {
            double mid = (L + R) / 2.0;
            int k = ceil(mid);
            t1 = t2 = 0.0;
            query(k, 100000, 1, 100000, Tree[l - 1], Tree[r]);
            double cal = (S[r] - S[l - 1] - t1) + mid * t2;
            if (cal < t)
                L= mid;
            else
                R = mid;
        }
        printf("%.7f\n", R);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。