noip模拟赛 fateice-shop

题目背景

紫女，韩国歌舞坊（实为刺客组织）紫兰轩之主，千娇百媚，美艳无方。武艺高强且极有谋略胆识，精通奇石药物，冶炼之术及制毒用毒之术独步天下，真实姓名与来历无人知晓，只因总是身着一袭紫衣，所以众人以“紫女”称之。与公子韩非共同创建了“流沙”组织。

题目描述

为了能够获取更多的韩国内部消息，紫女决定收购一批极为罕见的稀世珍宝在紫兰轩进行拍卖，以吸引更多的大人物前来紫兰轩。她准备在m天内购买一些宝物来充实库存。现在，市场上有n种物品，第i种物品的价格为vi，紫女每天最多只能购买xi个。第i天紫女得到wi的钱，她会选择不停购买能买得起的最贵的物品。她想在尽量短的时间内做出决断，所以她需要提前求出每天会购买多少个物品。

由于持有现金非常的危险，每一天买完东西后如果还剩下钱，这些钱就会被丢弃。

输入输出格式

输入格式：

第一行两个整数n,m。接下来n行每行两个整数vi,xi。接下来m行每行一个整数wi。

输出格式：

m行每行一个整数，第i行表示第i天购买的物品数量。

输入输出样例

输入样例#1：

输出样例#1：

2
4
6

说明

对于20%的数据，n,m<=1000。

对于另外40%的数据，xi=1。

对于100%的数据，n,m<=100000，1<=vi<=10^9，1<=xi<=10000，0<=wi<=10^18。

分析：主要的思想还是二分吧.

每次要找到<=w的最大的价格，我们可以先对原序列按照价格排个序，然后二分来找.找到以后我们看从这个物品往前买能买到哪，买多少个，这里可以用前缀和+二分解决，如果当前商品买不完就计算一下能买多少个.每次下来w都会减小，我们就不断地缩小右边界不停地二分就可以了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

struct node
{
    ll v, x;
}e[100010];

ll n, m;
ll sum[100010], w, sum2[100010],ans;
bool flag = false;

bool cmp(node a, node b)
{
    return a.v < b.v;
}

int erfen(ll maxn)
{
    ll pos = 0, pos2 = 0;
    ll l = 1, r = maxn;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (e[mid].v <= w)
        {
            pos = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    if (!pos)
    {
        flag = 1;
        return 0;
    }
    l = 1, r = pos;
    pos2 = pos;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (sum[pos] - sum[mid] <= w)
        {
            pos2 = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    w -= sum[pos] - sum[pos2];
    ans += sum2[pos] - sum2[pos2];
    ll use = e[pos2].x;
    
    while (w >= e[pos2].v && use)
    {
        use--;
        w -= e[pos2].v;
        ans++;
    }
    if (use == 0)
        return pos2 - 1;
    else
        return pos2;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &e[i].v, &e[i].x);
    sort(e + 1, e + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + e[i].v * e[i].x;
        sum2[i] = sum2[i - 1] + e[i].x;
    }
    while (m--)
    {
        flag = 0;
        scanf("%lld", &w);
        ans = 0;
        int t = erfen(n);
        while (!flag && w >= e[1].v && t > 0)
            t = erfen(t);
        printf("%lld
", ans);
    }

    return 0;
}