数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中将数组平均分割所需的最小正整数
问题陈述
给定一个包含 N 个正整数的数组，任务是找到可以放置在数组任意两个元素之间的最小正整数，使得在它之前出现的子数组的元素之和等于在它之后出现的子数组的元素之和，并且新放置的整数包含在两个子数组中的任意一个。
示例
如果 arr = {3, 2, 1, 5, 7, 10}，则输出为 6。如果我们在 5 和 7 之间放置值 6，则左右子数组的和将如下所示相等：
+ 2 + 1 + 5 + 6 = 17
7 + 10 = 17
算法
- 设整个数组的和为 S
- 思路是找到直到索引 i（包括 i）的左侧和。设此和为 L
- 现在，子数组 arri+1 .. N 的和为 S – L。设此和为 R
- 由于这两个子数组的和应该相等，因此上述获得的两个和 L 和 R 中较大的一个，应该减少到这两个和中较小的值的程度，而较大值和较小值之间的差值，将是所需的正整数的值。
示例
#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
int sum = 0;
sum = accumulate(arr, arr + n, sum);
int leftSum = 0;
int rightSum = 0;
int minValue = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
leftSum += arr[i]; rightSum = sum - leftSum;
if (leftSum > rightSum) {
int e = leftSum - rightSum;
if (e < minValue) {
minValue = e;
}
} else {
int e = rightSum - leftSum;
if (e < minValue) {
minValue = e;
}
}
}
return minValue;
}
int main() {
int arr[] = {3, 2, 1, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int minValue = getMinimumSplitPoint(arr, n);
cout << "Element " << minValue << " needs to be inserted\n";
return 0;
}输出
编译并执行上述程序时，它会生成以下输出：
Element 6 needs to be inserted
更新于： 2019年11月22日
163 次查看
广告