資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告