自动搬运

查看原文

来自洛谷，原作者为

	Just_do_it **

搬运于2025-08-24 21:40:40，当前版本为作者最后更新于2018-03-08 10:53:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

我们将收益表达出来是$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$来更新增加的收益

代码:

#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;
}