题解：P2707 Facer 帮父亲

对于门票价格的分配，我们可以一元一元地分配，每次显然要分配到最优的景点。

考虑每个景点在当前收益下获得一元分配后收益的增加量。

若当前的收益为 w_1=x \times ( a - b \times x ) ，则再获得一元分配后的收益 w_2=(x+1)\times [a-b\times(x+1)]，那么增加量 d=w_2-w_1，每次分配到 d 最大的景点。

将景点放到堆里按 d 排序，每次取出来处理完再放回去即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char c=getchar();ll x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
struct node{
    ll a,b,x,d,id;
}p[N];
struct cmp{
    inline bool operator()(node a,node b)
    {
        if(a.d<b.d) return 1;
        return 0;
    }
};
priority_queue<node,vector<node>,cmp> da;
ll m,n,k,ans=0;
int main()
{
    n=read();
    k=read();
    for(int i=1;i<=n;i++)
    {
        p[i].a=read(); 
        p[i].b=read();
        p[i].id=i;
        p[i].x=0;
        p[i].d=(p[i].x+1)*max((p[i].a-p[i].b*(p[i].x+1)),1ll*0)-p[i].x*max((p[i].a-p[i].b*p[i].x),1ll*0);
        da.push(p[i]);
    }
    for(int i=1;i<=k;i++)
    {
        node y;
        y=da.top();
        ll id=y.id;
        da.pop();
        p[y.id].x++;
        p[y.id].d=(p[id].x+1)*max((p[id].a-p[id].b*(p[id].x+1)),1ll*0)-p[id].x*max((p[id].a-p[id].b*p[id].x),1ll*0);
        da.push(p[id]);
    }
    for(int i=1;i<=n;i++)
    {
        ans+=p[i].x*max((p[i].a-p[i].b*p[i].x),1ll*0);
    }
    cout<<ans;
    return 0;
}