题目背景
是一个勤工俭学的好孩子,暑假的时候他来到一个旅游公司打工赚外快(冲
STEAM )。假期来景点游玩的人非常多,于是他的老板想调整一下票价,好让游客们满
意,同时又要尽可能多赚些钱。按照正常的操作,这个任务,没错,又到了 YY 头上,于
是 YY 又来找你帮忙了 ......
YY
题目描述
这个公司一共管理着 n 个景点,每个景点的票价和参观人数呈一个固定的函数关系。具
体地说,如果该景点的票价为 x ,则该景点会有 a i − b i × x 个游客来游玩。那么在所有
景点的总票价不超过 m 的情况下,请你安排一个方案使得赚到的钱最多。输入格式
从文件 work.in 中读入
第一行两个正整数 n, m ,含义如上。
接下来 n 行每行两个正整数 a i , b i 表示每个景点的参数。
输出格式
输出到 work.out 文件中
共一行,表示最多能赚到的钱数。
样例
输入
2 4
50 2
40 1
输出
171
数据范围
对于 100% 的数据: 1 ≤ n, m ≤ 100000, 1 ≤ a i , b i ≤ 100000
对于 20% 的数据: 1 ≤ n, m ≤ 200
对于另外 10% 的数据: m = 1
对于另外 30% 的数据: a − b ≤ 1, m ≤ n
这道题的思路其实挺明显的，我们不去想怎么直接给每个景点分配多少票价，而是将票价一个一个的给景点。
这其中就有贪心的思想，我们保存每次最大可以多获得多少价格（函数知识），用堆来维护就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define il inline
#define db double
using namespace std;
il int gi()
{
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
struct node
{
int b,v;
}no[1000045],heap[1000045];
int size;
il void push(node x)
{
heap[++size]=x;
int now=size,next;
while(now!=1)
{
next=now>>1;
if(heap[next].v>heap[now].v)
break;
swap(heap[next],heap[now]);
now=next;
}
}
il void pop()
{
heap[1]=heap[size--];
int now=1,next;
while(now<<1<=size)
{
next=now<<1;
if(heap[next+1].v>heap[next].v)
next++;
if(heap[next].v<heap[now].v)
break;
swap(heap[next],heap[now]);
now=next;
}
}
int main()
{
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
int n=gi(),m=gi();
int x,y;
for(int i=1;i<=n;i++)
{
x=gi(),y=gi();
if(x-y>0)
{
no[i].b=y;
no[i].v=x-y;
push(no[i]);
}
}
ll ans=0;
for(int i=1;i<=m;i++)
{
if(!size)
break;
node now=heap[1];
pop();
ans+=now.v;
now.v-=(now.b<<1);
if(now.v<=0)
continue;
push(now);
}
printf("%lld
",ans);
return 0;
}