CFR-634E Restorer Distance 题解

题目大意

给你n个墙壁的高度，你可以花a块钱让墙壁高度减一，也可以花r块钱让墙壁高度减一，还可以花m块钱让高的墙壁转移一个高度给矮的墙壁，问你让墙壁的高度全都相等所花费的最小代价为多少。

解题思路

看到题目就知道是我不会写的题目。。

（其实之前是听过三分的，但是没有去学过。。

刚好补题的时候去学一下三分。

三分其实和二分很相似，都是将一块区间分隔开来，二分是分成两份，三分是分成三份，通过一步步排除区间来缩小时间复杂度。

但是二分适用于单调函数，三分适用于二次函数，可以用来求出二次函数的最值。

对于三分来说，凹函数和凸函数的情况是不一样的。

那对于这个题目来说，我们可以用三分来搜索某一个高度来使其他的墙等于这个高度的代价最小，很显然，这个关于h的函数是一个凹函数。

在计算花费时，我们可以先算出添加的数量和减少的数量，如果$m<a+r$，那么肯定优先选择m，然后剩下的乘以a或者r。

否则直接按照a和r来计算。

三分模板

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
int h[N],n,a,R,m;

ll check(int t) {
	ll add, minu, ans;
	add = minu = ans = 0;
	for (int i = 1; i <= n; i++) {
		if (t >= h[i])	add += t - h[i];//需要添加的数量
		else minu += h[i] - t;//需要减小的数量
	}
	if (m < a + R) {
		ll x = min(add, minu);
		ans += x * m;
		if (add >= minu)	ans += a * (add - x);
		else ans += R * (minu - x);
	}
	else ans += add * a + minu * R;
	return ans;
}

int main() {
	int l = 0, r = 0;
	cin >> n >> a >> R >> m;
	for (int i = 1; i <= n; i++)	cin >> h[i],r = max(r,h[i]);//区间的最大值为高度的最大值
	while (l < r) {//l==r的时候退出
		int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
		if (check(mid1) >= check(mid2))	l = mid1 + 1;
		else r = mid2 - 1;
	}
	cout << check(l) << endl;
}