<![CDATA[

题目描述

蛤布斯有n种商品，第i种物品的价格为ai，价值为bi。有m个人来向蛤布斯购买商品，每个人每种物品只能购买一个。第j个人有cj的钱，他会不停选择一个能买得起的价格最高的商品买走（如果有多个则选择价值最高的）。你需要求出每个人购买的物品的价值和。

思路

我们首先想到二分一个最大可以买到的值，然后在二分一下以当前值为起点，一共可以买多少连续的商品

#include <stdio.h>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) 
#define N 100001
#define LL long long
struct arr
{
    LL c, w;
}a[N];
LL totc[N], totw[N];
inline LL read()
{
    LL x = 0, p = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
    return x * p;
}
inline void write(LL x)
{
    if (x < 10) putchar(x + '0');
    else
    {
        write(x / 10);
        write(x % 10);
    }
}
int cmp(arr a, arr b)
{
    if (a.c > b.c) return 1;
    if (a.c < b.c) return 0;
    if (a.c == b.c) return a.w > b.w;
}
int main()
{
    LL n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = (arr) {read(), read()};
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        totc[i] += totc[i - 1] + a[i].c;
        totw[i] += totw[i - 1] + a[i].w;
    }
    for (int q = 1; q <= m; q++)
    {
        LL x = read();
        LL l = 1, r = n, st, ans = 0;
        int fl = 1;
        while (fl)
        {
            fl = 0;
            while (l <= r)
            {
                LL mid = (l + r) >> 1;
                if (a[mid].c <= x)
                {
                    st = mid;
                    fl = 1;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            l = st + 1;
            r = n;
            LL ed = st;
            while (l <= r)
            {
                LL mid = (l + r) >> 1;
                if (totc[mid] - totc[st - 1] <= x)
                {
                    ed = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if (!fl) break;
            x -= totc[ed] - totc[st - 1];
            ans += totw[ed] - totw[st - 1];
            l = ed + 1;
            r = n;
        }
        write(ans);
        putchar('\n');
    }
}