Shop

有 n 种物品，第 i 种物品的价格为 vi，每天最多购买 xi 个。

有 m 天，第 i 天你有 wi 的钱，你会不停购买能买得起的最贵的物品。你需要求出你每天会购买多少个物品。

【输入格式】

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

wi

【输出格式】

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

【输入样例】

3 3

1 1

2 2

3 3

5

10

15

【输出样例】

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。

考试唯一A掉的题。。。

预处理出从大到小的后缀和，先查询出最前面能买多少，买完之后有一个性质是之后每买一种商品剩下的钱至少减去一半。

这样的话只需要logw次lower_bound查询就行了。

代码：

#include
    
     #define N 100005#define ll long longusing namespace std;inline ll read(){    ll ans=0;    char ch=getchar();    while(!isdigit(ch))ch=getchar();    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans;}inline void write(ll x){    if(x>9)write(x/10);    putchar((x%10)^48);}int n,m;ll sum[N],a[N],b[N],num[N];struct Node{ll v,x;}p[N];inline bool cmp(Node a,Node b){
   return a.v
     
      =1&&w>=p[1].v){            int ppos=pos;            pos=lower_bound(b+1,b+pos+1,w)-b;            if((p[pos].v>w)||pos>ppos)--pos;            if(pos<1)break;            ll tmp=min(p[pos].x,w/p[pos].v);            w-=p[pos].v*tmp,ans+=tmp;            --pos;        }        write(ans),puts("");    }    return 0;}