洛谷 2707: Facer帮父亲

2018-03-08Chentiancai_nn?

题目背景

Facer可是一个孝顺的孩纸呦

题目描述

Facer的父亲是一名经理,现在总是垂头丧气的。

Facer问父亲,怎么啦?父亲说,公司出了点问题啊。

公司管理着N个风景点,每个风景点都有不少人来参观。

可是现在!人民投诉票价太高了,他不得不调整票价

具体来说,第i个景点如果票价是x,来的人数就是$MAX( (a_i - b_i \times x),0 )$[收益自己算好伐]

你需要分配每个景点的门票,使得每个景点门票总和不超过k,且最大化收益

求最大的收益

输入输出格式

输入格式:

第一行N , k

接下来N行,每行ai,bi

输出格式:

一行,最大的收益

输入输出样例

输入样例#1:

2 4
50 2
40 1

输出样例#1:

171

说明

样例解释:

景点$1$票价$3$,景点$2$票价$1$

景点$1$人数:$50 - 3 \times 2 = 44$ 票价 :$3$ 收益:$132$

景点$2$人数 :$40 - 1 \times 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 提供解法

题解

思路:

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

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

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

$x$增加1之后的收益$v_2 = (x+1)(a-b(x+1)) = (ax - bx^2) + a-b-2bx$

$x$增加$1$之后的收益增加值$\Delta v = v_2-v_1 = a-b-2bx $

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

且$\Delta v$的改变量为

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close