洛谷P2707 Facer帮父亲 [优先队列，数学]

　　题目传送门

Facer帮父亲

题目背景

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 提供解法

---

　　分析：

　　首先我们分析一下，实际上给定的景点的$a$和$b$就是二次函数的两个参数，我们可以计算得到，一个景点的票价每增加$1$获得的收益会变化的数值是：

$a(x+1)-b(x+1)^2-(ax-bx^2) $
$=ax+a-bx^2-2bx-b-ax+bx^2 $
$=a-b-2bx$

　　那么就好办了，我们只需要求出$x$为$1$的情况，然后放入优先队列中维护，每次取出最大的统计答案，然后更新数值继续放入堆中维护。当然，每一次的增加值实际上只有$a-b-2bx-(a-b-2b(x+1))=2b$，所以直接把取出值减去2b就行了。

　　Code：

//It is made by HolseLee on 16th Oct 2018

//Luogu.org P2707

#include<bits/stdc++.h>

using namespace std;

int n,m;

long long ans;

struct Node {

    int b,v;

    bool operator < (const Node x) const {

        return v<x.v;

    }

};

priority_queue<Node> q;

inline int read()

{

    char ch=getchar(); int num=; bool flag=false;

    while( ch<'' || ch>'' ) {

        if( ch=='-' ) flag=true; ch=getchar();

    }

    while( ch>='' && ch<='' ) {

        num=num*+ch-''; ch=getchar();

    }

    return flag ? -num : num;

}

int main()

{

    n=read(); m=read();

    Node now;int x,y;

    for(int i=; i<=n; ++i) {

        x=read(), y=read();

        if( x-y> ) q.push((Node){y,x-y});

    }

    while( (m--) && (!q.empty()) ) {

        now=q.top(); q.pop();

        ans+=now.v; now.v-=(*now.b);

        if( now.v<= ) continue;

        q.push(now);

    }

    printf("%lld\n",ans);

    return ;

}