洛谷P2707 Facer帮父亲 [优先队列,数学]
Facer帮父亲
题目背景
Facer可是一个孝顺的孩纸呦
题目描述
Facer的父亲是一名经理,现在总是垂头丧气的。
Facer问父亲,怎么啦?父亲说,公司出了点问题啊。
公司管理着N个风景点,每个风景点都有不少人来参观。
可是现在!人民投诉票价太高了,他不得不调整票价
具体来说,第i个景点如果票价是x,来的人数就是max( (ai - bi * x),0 )[收益自己算好伐]
你需要分配每个景点的门票,使得每个景点门票总和不超过k,且最大化收益
求最大的收益
输入输出格式
输入格式:
第一行N , k
接下来N行,每行ai,bi
输出格式:
一行,最大的收益
输入输出样例
2 4
50 2
40 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 ;
}
最新文章
- 关于几个主流语音SDK的接入问题
- codevs 1472 体检
- (原创)Windows系统后安装ubuntu,无法选择启动ubuntu。
- if 判断中出现逗号
- 组合数(Lucas定理) + 快速幂 --- HDU 5226 Tom and matrix
- android webview 介绍
- Using Amazon API Gateway with microservices deployed on Amazon ECS
- Uncaught TypeError: Illegal constructor(&hellip;)
- 阻塞、非阻塞的概念和select函数的阻塞功能
- Asp.net 管道事件
- hdu 1543 Paint the Wall
- Asp.Net中使用Couchbase——Memcached缓存使用篇
- [ZJOI 2010]count 数字计数
- C++之IO操作
- 以Windows服务方式运行ASP.NET Core程序
- hadoop_随笔二_参数
- DK location not found. Define location with sdk.dir in the local.properties file or with an ANDROID_HOME
- Centos 6.5 freeswitch 编译mod_shout
- python基础一 ------如何获取多个字典相同的键
- DLL 调试(C# 调用 C++ 的 DLL)