小核桃有 nn 个数字,他可以使用魔法将数字的大小改变。假设他的法力值是 x(1 \leq x \leq 10^{9})x(1≤x≤10 9 ),那么对于每个数字而言,他都可以将这个数字增加或者减少 1 \sim x1∼x,修改数字不消耗法力值。 具体来说,如果一个数字为 2,小核桃的法力值为 3,那么他可以将这个数字减少 1 \sim 31∼3,或者增加 1 \sim 31∼3,即这个数字可能会变为 -1,0,1,3,4,5−1,0,1,3,4,5。当然,小核桃也可以不使用法力,使得这个数字保持不变。 小核桃想要把所有数字变成一样的,害怕法力值太高反噬身体,所以他想知道最低需要多少法力值可以将这些数字变成一样。C++
时间: 2024-02-16 22:03:50 浏览: 24
这是一个典型的贪心问题,我们可以先求出这 nn 个数字的中位数,然后把所有数字变成中位数即可。因为如果一个数字比中位数小 kk,那么它变成中位数需要增加 kk,另外一个数字变成中位数需要减少 kk,总共需要增加减少 2k2k,而中位数比它们都要小,所以我们可以只考虑增加操作,即把小的数变成中位数。因为中位数是中间的数,所以我们只需要把所有数字排序后找到中间的那个数即可。时间复杂度 O(n\log n)O(nlogn)。
C++ 代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n);
int mid = a[n / 2], res = 0;
for (int i = 0; i < n; i ++ ) res += abs(a[i] - mid);
cout << res << endl;
return 0;
}
```
相关问题
$-V_{ref} \leq x \leq V_{ref}$ 这是什么
$-V_{ref} \leq x \leq V_{ref}$ 表示信号幅值 $x$ 的取值范围在 $-V_{ref}$ 到 $V_{ref}$ 之间(包括两端点)。其中,$V_{ref}$ 表示参考电压或参考幅值,是均匀量化中的一个重要参数,决定了量化的范围和量化精度。在实际应用中,参考电压可以通过电路设计或外部设置来确定,通常需要根据信号的动态范围和噪声等特性进行选择。
1到33随机选取五个数字,概率最大的五组数字为?
由于每个数字被选中的概率相等,因此我们可以使用组合数学的知识来计算概率。
首先,有 $C_{33}^5$ 种选取五个数字的不同组合方式。
然后,我们需要计算每个数字被选中的次数。由于我们要选取五个数字,因此每个数字最多被选中五次。因此,我们可以列出如下的表格:
| 数字 | 被选中次数 |
|------|-------------|
| 1 | $k_1$ |
| 2 | $k_2$ |
| ... | ... |
| 33 | $k_{33}$ |
其中,$k_1, k_2, ..., k_{33}$ 表示每个数字被选中的次数。
由于每个数字最多被选中五次,因此我们有以下限制条件:
$$k_1 + k_2 + ... + k_{33} = 5$$
$$0 \leq k_i \leq 5 \quad (1 \leq i \leq 33)$$
根据组合数学的知识,我们可以计算出每种选取方式对应的概率为:
$$P = \frac{1}{C_{33}^5}$$
现在的问题是如何找到概率最大的五组数字。这个问题可以通过枚举所有的数字组合来解决。具体来说,我们可以对 $k_1, k_2, ..., k_{33}$ 进行枚举,然后计算对应的概率。最后,我们可以选择概率最大的五组数字作为答案。
由于这个计算量非常大,因此我们可以使用计算机来进行计算。下面是 Python 代码实现: