cf round 643 E

最新推荐文章于 2025-02-12 18:46:15 发布

FawkesLi

最新推荐文章于 2025-02-12 18:46:15 发布

阅读量219

点赞数

分类专栏：算法算法-二分好题

本文链接：https://blog.csdn.net/Fawkess/article/details/106171805

版权

算法同时被 3 个专栏收录

143 篇文章

订阅专栏

好题

19 篇文章

订阅专栏

算法-二分

6 篇文章

订阅专栏

探讨了一种算法，用于解决使一组数值相等的最小成本问题，通过三种操作：增加、减少或交换数值，每种操作有固定成本。采用二分搜索策略找到最佳中间值，确保整体操作成本最低。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：
告诉你n,a,r,m,然后给你n个数，要求你把这n个数变得一样大。你可以进行三种操作，给某个数+1,或者给某个数-1,或者把某个数移动1到另一个数(任选两个数，一个+1,一个-1)，这三种操作的代价分别是a,r,m。问你要达成目标的最小代价。

输入1
3 1 100 100
1 3 8
输出1
12

输入2
5 1 2 2
5 5 3 6 5
输出2
3

思路：
首先考虑把所有数都变成x的代价是最小的，那么min(a[i])<x<max(a[i]),假设我们已知x，那么我们就可以暴力的计算代价（即大于x就直接减，小于x就直接加，能换位就换位）。这种是最优的，因为x是最优的，所以结果是最优的。

而且我们可以发现一个规律，如果我们假设最优解是k，k>x,那么k的代价一定大于x的代价，k<x，k的代价也会大于x的代价。将假设最优点视为x轴，对应的代价视为y轴，那么函数图像应该是这样的

在这里插入图片描述
很明显在x的左侧，函数斜率小于0，右侧函数斜率大于0，那么我们就可以根据此条性质二分答案。这里复习一下二分的要点

 1.代价关于假设有明显单调关系，且满足左侧都可行，右侧都不可行的情况可以二分

这道题中，函数的斜率就是明显关于假设的k值单调的（斜率是单增的）。而且我们要找的是斜率为0的点，也就是斜率小于等于0且斜率最大的点，这样就满足左侧都可行，右侧都不可行，所以这是一个标准的二分算法。

代码第51行输出lift的值作为答案。这里有的同学可能就会问了，为什么二分的答案有时候输出lift的值，有时候输出right的值？这里再复习一下二分问题的边界输出要点

mid赋值给谁，谁就是最终答案

二分条件是c(mid) > c(mid + 1)，这个条件满足的时候mid和mid+1谁更可能是最终答案呢？明显是mid+1，因为c(mid) > c(mid + 1)啊，这时候我们将mid+1赋值给l，所以最后l是最终答案。
（你也可以随便举个例子带入验证一下，考虑到整型精度都是向下取整的问题，通常我们都将lift作为最终答案，也有的奇葩喜欢强行right，满足逻辑就行）

code：
（注意int会爆）

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <stack>

#define INF 0x3f3f3f3f
#define IMAX 2147483646
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int

using namespace std;

ll n, a, r, m, arr[111111];

ll c(ll x) {
	ll o = 0, p = 0;
	for (int i = 0; i < n; i++) 
		if (arr[i] > x)o += arr[i] - x;
		else p += x - arr[i];
	
	ll op = min(o, p), res = 0;
	res += min(op*m, op*(a + r));
	res += (o - op)*r;
	res += (p - op)*a;
	return res;
}

int main() {
	scanf("%lld%lld%lld%lld", &n, &a, &r, &m);
	ll l = IMAX, r = 0,mid;
	for (int i = 0; i < n; i++)
		scanf("%lld", arr + i), l = min(arr[i], l), r = max(arr[i], r);

	while (l < r) {
		mid = (l + r) / 2;
		if (c(mid) > c(mid + 1))
			l = mid + 1;
		else r = mid;
	}
	printf("%lld\n", c(l));

	return 0;
}