資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查一條45度線是否可以將平面分成兩個重量相等的部分（使用C++）
假設我們有n個不同的二維座標點(Xi, Yi)，每個點都有一個權重Wi，我們必須檢查是否可以繪製一條45度角的線，使得每個側面的點權重之和相同。
所以，如果輸入類似於[[-1,1,3],[-2,1,1],[1,-1,4]]，則輸出為True。
為了解決這個問題，我們將遵循以下步驟：
- n := v的大小
- 定義一個對映weight_at_x
- max_x := -2000, min_x := 2000
- for i := 0 to n-1 do:
- temp_x := v[0, i] - v[1, i]
- max_x := max(max_x, temp_x)
- min_x := min(min_x, temp_x)
- weight_at_x[temp_x] := weight_at_x[temp_x] + v[2, i]
- 定義一個數組sum_temp
- 在sum_temp末尾插入0
- for x := min_x to max_x do:
- 在sum_temp末尾插入(sum_temp的最後一個元素 + weight_at_x[x])
- total_sum := sum_temp的最後一個元素
- partition_possible := false
- for i := 1 to sum_temp的大小-1 do:
- if sum_temp[i] == total_sum - sum_temp[i] then:
- partition_possible := true
- if sum_temp[i - 1] == total_sum - sum_temp[i] then:
- partition_possible := true
- if sum_temp[i] == total_sum - sum_temp[i] then:
- return partition_possible
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void is_valid_part(vector<vector<int>> &v){
int n = v.size();
map<int, int> weight_at_x;
int max_x = -2000, min_x = 2000;
for (int i = 0; i < n; i++) {
int temp_x = v[0][i] - v[1][i];
max_x = max(max_x, temp_x);
min_x = min(min_x, temp_x);
weight_at_x[temp_x] += v[2][i];
}
vector<int> sum_temp;
sum_temp.push_back(0);
for (int x = min_x; x <= max_x; x++) {
sum_temp.push_back(sum_temp.back() + weight_at_x[x]);
}
int total_sum = sum_temp.back();
int partition_possible = false;
for (int i = 1; i < sum_temp.size(); i++) {
if (sum_temp[i] == total_sum - sum_temp[i])
partition_possible = true;
if (sum_temp[i - 1] == total_sum - sum_temp[i])
partition_possible = true;
}
printf(partition_possible ? "TRUE" : "FALSE");
}
int main() {
vector<vector<int>> v = {{-1,1,3},{-2,1,1},{1,-1,4}};
is_valid_part(v);
}輸入
{{-1,1,3},{-2,1,1},{1,-1,4}}輸出
TRUE
更新於：2020年8月27日
91 次檢視
廣告