AcWing 800. 数组元素的目标和
原题链接
简单
作者:
华尔采尔
,
2024-01-15 11:36:21
,
所有人可见
,
阅读 29
#include <iostream>
#include <vector>
using namespace std;
// 在数组 arr 中找到小于等于 target 的最大值的下标
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
int n, m, x;
cin >> n >> m >> x;
vector<int> A(n);
vector<int> B(m);
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
for (int j = 0; j < m; ++j) {
cin >> B[j];
}
// 遍历数组 A,对于每个 A[i],在数组 B 中二分查找 x - A[i] 的位置
for (int i = 0; i < n; ++i) {
int target = x - A[i];
int j = binarySearch(B, target);
// 如果找到了合适的数对,则输出答案并结束程序
if (j != -1 && A[i] + B[j] == x) {
cout << i << ' ' << j << endl;
return 0;
}
}
// 如果没有找到合适的数对,输出提示信息
cout << "No solution found." << endl;
return 0;
}