C++语言有一些细长的棍子的任务是修改棍子,使每个棍子的长度相同。 你可以加长或缩短每根棍子。两个操作的成本都是xx,其中xx是新长度和原始长度之间的差值。 最低总成本是多少? 输入 第一个输入行包含一个整数nn:棒的数量。 然后是nn个整数:p1,p2,…,pnp1,第2页,…,伪随机数: 棍子的长度。 输出 打印一个整数:最小总成本。 限制 1≤n≤2·105 1≤pi≤109 样品 输入副本输出副本 5. 2 3 1 5 2 5.
时间: 2024-02-25 13:54:20 浏览: 133
cocos2dx3.0 英雄难过棍子关源码
4星 · 用户满意度95%
这道题可以使用贪心算法来解决。我们需要先计算出所有棍子的平均长度,然后对于每个棍子,计算它与平均长度的差值,然后将所有差值的绝对值相加即为最小总成本。
具体实现步骤如下:
1. 读入棒的数量和长度。
2. 计算所有棒的长度之和,并计算平均长度。
3. 对于每个棒,计算它与平均长度的差值,并将差值的绝对值累加到总成本中。
4. 输出总成本。
以下是 C++ 的实现代码:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
int avg = sum / n;
int cost = 0;
for (int i = 0; i < n; i++) {
cost += abs(a[i] - avg);
}
cout << cost << endl;
return 0;
}
```
注意,这里使用了 `vector` 容器来存储棒的长度,可以避免手动管理内存的问题。同时,使用了标准库函数 `abs` 来计算差值的绝对值。
阅读全文