问题描述

小 C 今天出去购物,商店里总共有 n 种商品,小 C 的钱够买至多 k 个商品。

小 C 对每种商品都有一个喜爱程度,但如果买了同一种商品很多次,小 C 对这种商品的喜爱程度就会降低。

具体地说,如果小 C 买了 x 个第 i 种商品,每个第 i 种商品都会让他增加 max(ai−xbi,0)的喜悦值。请你求出小 C 最多能增加多少喜悦值。

输入格式

第一行两个正整数 n, k。

接下来 n 行,每行两个正整数 ai , bi。

输出格式

输出一个整数,表示答案。

样例输入

2 4

50 2

40 1

样例输出

171

数据范围

对于 50%的数据,n,k ≤1000 。

对于 100%的数据,n, k, ai ≤10 5 ,bi ≤1000。

解析

设第\(k\)次购买第\(i\)件商品，那么新购得的商品增加的开心值为\(a[i]-k*b[i]\)，而前面的商品本来可以增加\((k-1)*[a[i]-(k-1)*b[i]]\)的开心值，由于又买了一次，一共减少了\((k-1)*b[i]\)的值，所以，这件商品的贡献为\(a[i]-(2k-1)*b[i]\)。由贪心的思想，用堆维护每次的最大值，每弹出一个值就将对应的商品的新的贡献放进堆中。

代码

#include 
    
     #include 
     
      #include 
      
       #define N 100002#define int long longusing namespace std;struct con{    int a,b,id,cost;    bool operator < (const con &x) const{        return cost
       
         q;int read(){    char c=getchar();    int w=0;    while(c<'0'||c>'9') c=getchar();    while(c<='9'&&c>='0'){        w=w*10+c-'0';        c=getchar();    }    return w;}signed main(){    freopen("buy.in","r",stdin);    freopen("buy.out","w",stdout);    n=read();k=read();    for(i=1;i<=n;i++){        c[i].a=read();c[i].b=read();        c[i].id=i;cnt[i]++;        c[i].cost=c[i].a-c[i].b;        q.push(c[i]);    }    int ans=0;    for(i=1;i<=k;i++){        con tmp=q.top();        q.pop();        ans+=tmp.cost;        cnt[tmp.id]++;        tmp.cost=tmp.a-(2*cnt[tmp.id]-1)*tmp.b;        if(tmp.cost<0) tmp.cost=0;        q.push(tmp);    }    cout<
        
         <
        
       
      
     
    

P.S. 注意long long......