数据结构
网络
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
广告