题解 P2707 【Facer帮父亲】

Just_do_it · 2018-03-08 10:53:20 · 题解

思路：

我们将收益表达出来是v = ax - bx^2 这是一个二次函数，在二次函数的对称轴之前函数单调递增但斜率不断变小，及x每增加1所增加的v会不断变小。因此我们将所有当前门票增加所增加的收益放进大根堆里，贪心每次加最大的那个，重新计算后加入堆。

当然没有函数基础的人可以这么想

当前收益v_1 = x(a-bx) = ax - bx^2

我们发现\Delta v在x的增加后不断变小，可以贪心每次增加最大的收益增加值的x。

且\Delta v的改变量为

这个改变量与x没有关系，只用记b来更新增加的收益

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline void read(int &x){
    int f = 1;x = 0;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
    x *= f;
}

const int N = 100005;
int n,k;
ll ans;
struct node{
    int val,b;
    friend bool operator <(node a,node b){
        return a.val < b.val;
    }
}u;
priority_queue<node> Q;

int main(){
    read(n); read(k);
    for(int i = 1,a,b;i <= n;++i){
        read(a),read(b);
        if(a-b > 0) Q.push((node){a-b,b});
    }
    while((k--) && (!Q.empty())){
        u = Q.top(); Q.pop();
        ans += u.val; u.val -= 2*u.b;
        if(u.val <= 0) continue;
        Q.push(u);
    }
    printf("%lld\n",ans);
    return 0;
}