数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用C++重新排列数组以最大化i*arr[i]
在本文中，我们将讨论重新排列给定n个数字数组的问题。基本上，我们必须从数组中选择元素。对于每个选择的元素，我们会获得一些分数，这些分数将通过当前元素的值 * 之前选择的元素数量来计算。您应该选择元素以获得最高分。例如：
Input : arr[ ] = { 3, 1, 5, 6, 3 }
If we select the elements in the way it is given, our points will be
= 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
= 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
= 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
= 48(maximum)
Output : 48
Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63寻找解决方案的方法
观察示例，我们发现要获得最高分，我们需要从小到大选择元素。寻找解决方案的方法是：
- 将给定数组按升序排序。
- 从索引0开始选择元素到结尾。
- 计算选择每个元素获得的分数。
示例
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main () {
int arr[] = { 2, 4, 7, 1, 8 };
int n = sizeof (arr) / sizeof (arr[0]);
// sorting the array
sort (arr, arr + n);
int points = 0;
// traverse the array and calculate the points
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
}输出
Maximum points: 63
上述代码的解释
这段C++代码易于理解。首先我们对数组进行排序，然后使用for循环遍历数组，计算从头到尾选择每个元素获得的分数。
结论
在本文中，我们讨论了从数组中选择元素以获得最高分的问题，其中分数通过i * arr[i]计算。我们采用贪心算法来解决这个问题并获得最高分。还讨论了C++代码来实现相同的目的，我们也可以用其他语言（如C、Java、Python等）编写此代码。希望本文对您有所帮助。
更新于：2021年11月26日
868 次浏览
广告