数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中将数组平均分割
假设我们有一个数组 A，我们必须将 A 的每个元素移动到列表 B 或列表 C 中。（这些列表 B 和 C 最初为空。）我们必须检查这种移动之后，是否可能 B 的平均值等于 C 的平均值，并且 B 和 C 都非空。
因此，如果输入类似于 - [1,2,3,4,5,6,7,8,9,10]，则结果为真，
为了解决这个问题，我们将遵循以下步骤：
- n := A 的大小，total := 0
- for i := 0 to n-1 do −
- total := total + A[i]
- isPossible := false, m := n / 2
- for i := 1 to m while not isPossible do −
- if total * i % n == 0 then −
- isPossible := true
- if total * i % n == 0 then −
- if not isPossible then −
- return false
- 定义一个大小为 (total + 1) x (n / 2 + 1) 的二维数组 dp
- dp[0, 0] := true
- for i := 0 to n-1 do −
- x := A[i]
- for j := total downto x do −
- for l := 1 to (n / 2) do −
- dp[j, l] := dp[j, l] OR dp[j - x, l - 1]
- for l := 1 to (n / 2) do −
- for i := 1 to (n / 2) do −
- if (total * i) % n == 0 and dp[total * i / n, i] then −
- return true
- if (total * i) % n == 0 and dp[total * i / n, i] then −
- return false
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size();
int total = 0 ;
for(int i = 0; i < n; i++) total += A[i];
bool isPossible = false;
int m = n / 2;
for (int i = 1; i <= m && !isPossible; ++i)
if (total*i%n == 0) isPossible = true;
if (!isPossible) return false;
vector < vector <bool> > dp(total + 1, vector <bool>((n / 2) + 1));
dp[0][0] = true;
for(int i = 0; i < n; i++){
int x = A[i];
for(int j = total; j >= x; j--){
for(int l = 1; l <= (n / 2); l++){
dp[j][l] = dp[j][l] || dp[j - x][l - 1];
}
}
}
for(int i = 1 ; i <= (n / 2); i++){
if((total * i) % n == 0 && dp[total * i / n][i]) return true;
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
cout << (ob.splitArraySameAverage(v));
}输入
{1,2,3,4,5,6,7,8,9,10}输出
1
更新于：2020年6月2日
299 次浏览
广告