题目大意

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1
到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是：
1、给定 m 个区间[Li，Ri]；
2、选出一个参数 W；
3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：
这批矿产的检验结果 Y 为各个区间的检验值之和。即：
$$\sum_j 1\times \sum_j v_j,j\in[L_i,R_i]且w_j\geq W,j时矿石编号$$
若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小 T
不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近
标准值 S，即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。

解题关键

要把所有满足$w_j\geq W$的$\sum_j, \sum_j v_j$，一定要记得前缀和优化！这样就可以$O(n\log n)$解决，而不是$O(n^2\log n$了。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define UpdMax(x, y) x = max(x, y)

#define ll long long

const int MAX_N = 200010, MAX_Q = 200010;

const ll INF64 = 0x3f3f3f3f3f3f3f3fll;

ll W[MAX_N], V[MAX_N];

int L[MAX_N], R[MAX_N];

int N, TotQ;

ll Y, StdY;

ll GetY(ll w)

{

    static ll SumV[MAX_N];

    static int SumCnt[MAX_N];

    memset(SumV, 0, sizeof(SumV));

    memset(SumCnt, 0, sizeof(SumCnt));

    for (int i = 1; i <= N; i++)

    {

        SumV[i] = SumV[i - 1] + V[i] * (W[i] >= w);

        SumCnt[i] = SumCnt[i - 1] + (W[i] >= w);

    }

    ll y = 0;

    for (int q = 1; q <= TotQ; q++)

    {

        ll cnt = SumCnt[R[q]] - SumCnt[L[q] - 1], vSum = SumV[R[q]] - SumV[L[q] - 1];

        y += cnt * vSum;

    }

    return Y = y;

}

bool LeStdY(ll w)

{

    return GetY(w) <= StdY;

}

bool GeStdY(ll w)

{

    return GetY(w) >= StdY;

}

ll LowerBound(ll l, ll r, bool (*InUpperRange)(ll))

{

    if (!InUpperRange(r))

        return -1;

        while (l < r)

    {

        ll mid = (l + r) / 2;

        if (InUpperRange(mid))

            r = mid;

        else

            l = mid + 1;

    }

    InUpperRange(l);

    return l;

}

ll UpperBoundSubtract1(ll l, ll r, bool (*InLowerRange)(ll))

{

    if (!InLowerRange(l))

        return -1;

    while (l < r)

    {

        ll mid = (l + r + 1) / 2;

        if (InLowerRange(mid))

            l = mid;

        else

            r = mid - 1;

    }

    InLowerRange(l);

    return l;

}

int main()

{

    scanf("%d%d%lld", &N, &TotQ, &StdY);

    ll MaxW = 0;

    for (int i = 1; i <= N; i++)

        scanf("%lld%lld", W + i, V + i);

    for (int i = 1; i <= N; i++)

        UpdMax(MaxW, W[i]);

    for (int i = 1; i <= TotQ; i++)

        scanf("%d%d", L + i, R + i);

    Y = INF64;

    LowerBound(1, MaxW, LeStdY);

    ll y1 = Y;

    Y = INF64;

    UpperBoundSubtract1(1, MaxW, GeStdY);

    ll y2 = Y;

    printf("%lld\n", min(abs(y1 - StdY), abs(y2 - StdY)));

    return 0;

}

巴特西

luogu1314 聪明的质检员

题目大意

解题关键

最新文章

热门文章