题目背景
Facer可是一个孝顺的孩纸呦
题目描述
Facer的父亲是一名经理，现在总是垂头丧气的。
Facer问父亲，怎么啦？父亲说，公司出了点问题啊。
公司管理着N个风景点，每个风景点都有不少人来参观。
可是现在！人民投诉票价太高了，他不得不调整票价
具体来说，第i个景点如果票价是x，来的人数就是max( (ai - bi * x),0 )[收益自己算好伐]
你需要分配每个景点的门票，使得每个景点门票总和不超过k，且最大化收益
求最大的收益
输入输出格式
输入格式：
第一行N , k
接下来N行，每行ai,bi
输出格式：
一行，最大的收益
输入输出样例
输入样例#1：
2 4
50 2
40 1
输出样例#1：
171
说明
样例解释：
景点1票价3，景点2票价1
景点1人数：50 - 3*2 = 44 票价 :3 收益:132
景点2人数 : 40 - 1*1 = 39 票价 : 1 收益:39
总收益171 最大
10% n <= 5 , k <= 5
30% n <= 100,k <= 100
60% n <= 2000,k <= 2000
100%n <= 100000,k <= 100000
1 <= ai , bi <= 100000
鸣谢 zhouyonglong 提供解法solution：
本题模拟考试原题，比较简单的贪心。
我们贪心的去分配每$1$元票价，先把所有满足$a_i\geq b_i$的景点放入大根堆（不满足的显然不能分配），堆中的每个景点都记录下当前的收益，然后将分配$1$元后能得到最大收益的景点的票价$+1$，并累加增加的收益，然后重新入堆，直到当前票价$+1$后最大收益的景点收益为负或者$k$元分配完了为止。
贪心证明显然，时间复杂度$O(k\log n)$。
代码：
/*Code by 520 -- 10.30*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=1e5+;
ll n,m;
struct node{
ll a,b,x,lst;
bool operator < (const node &t) const {
return a*(x+)-b*(x+)*(x+)-lst<t.a*(t.x+)-t.b*(t.x+)*(t.x+)-t.lst;
}
};
priority_queue<node>q;
ll ans; int main(){
ios::sync_with_stdio();
cin>>n>>m; ll a,b,ppx;
For(i,,n) {
cin>>a>>b;
if(a>=b) q.push(node{a,b,,});
}
while(!q.empty()&&m--){
node tp=q.top(); q.pop();
ppx=tp.a*(tp.x+)-tp.b*(tp.x+)*(tp.x+)-tp.lst;
if(ppx<=) break;
tp.x++,tp.lst+=ppx; q.push(tp);
ans+=ppx;
}
cout<<ans;
return ;
}