資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究找出 n 個整數配對中最小差值差的 C++ 程式
假設，我們給定兩個陣列 a 和 b，分別包含 n 和 m 個值。我們必須使用兩個陣列中的值生成 n 個或 m 個對（以較小的為準）。一個對必須包含來自陣列 a 的一個值和來自陣列 b 的另一個值。我們必須生成這樣的對，使得對中的值的差值最小並且相同。我們將結果列印為輸出。
因此，如果輸入為 n = 4，m = 4，a = {2, 3, 4, 7}，b = {3, 4, 6, 5}，則輸出將為 1。
可以生成的配對為：
(3, 4), (4, 5), (7, 6), (2, 3).
所有對中的值的差值為 1。
步驟
為了解決這個問題，我們將按照以下步驟進行：
sort the array a Define an array s1 initialized with 0 Define an array s2 initialized with 0 for initialize i := 1, when i < n, update i := i + 2, do: insert last element of s1 + a[i] - a[i - 1] at the end of s1 for initialize i := 2, when i < n, update i := i + 2, do: insert last element of s2 + a[i] - a[i - 1] at the end of s2 ans := infinity for each value w in b, do: diff := first element in the array a not less than w - first value of a sub := last element of s1[diff / 2] + s2 ans := minimum of ans and sub print(ans)
示例
讓我們看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve(int n, int m, vector<int> a, vector<int> b){
sort(a.begin(), a.end());
vector<int> s1 = {0};
vector<int> s2 = {0};
for (int i = 1; i < n; i += 2)
s1.push_back(a[i] - a[i - 1] + s1.back());
for (int i = 2; i < n; i += 2)
s2.push_back(a[i] - a[i - 1] + s2.back());
int ans = INF;
for (const auto & w : b) {
int diff = lower_bound(a.begin(), a.end(), w) - a.begin();
int sub = s1[diff / 2] + s2.back() - s2[diff / 2] + abs(a[diff / 2 * 2] - w);
ans = min(ans, sub);
}
cout << ans << endl;
}
int main() {
int n = 4, m = 4;
vector<int> a = {2, 3, 4, 7}, b = {3, 4, 6, 5};
solve(n, m, a, b);
return 0;
}輸入
4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}輸出
1
更新於：2022 年 3 月 2 日
瀏覽量：182
廣告