AcWing 800. 数组元素的方针和
标题描述
给定两个升序排序的有序数组 A 和 B,以及一个方针值 x。
数组下标从 0 开端。
请你求出满意 A[i] B[j]=x 的数对 (i,j)。
数据确保有唯一解。
输入格局
榜首行包括三个整数 n,m,x,别离表示 A 的长度,B 的长度以及方针值 x。
第二行包括 n 个整数,表示数组 A。
第三行包括 m 个整数,表示数组 B。
输出格局
共一行,包括两个整数 i 和 j。
数据规模
数组长度不超过 10^5。
同一数组内元素各不相同。
1≤数组元素≤10^9
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
C
#include <iostream>
using namespace std;
const int N = 1e5 10;
int n, m;
long long x;
long long a[N], b[N];
int main() {
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ) scanf("%lld", &a[i]);
for (int i = 0; i < m; i ) scanf("%lld", &b[i]);
for (int i = 0, j = m - 1; i < n; i ) {
while (j >= 0 && a[i] b[j] > x) j--;
if (j >= 0 && a[i] b[j] == x) cout << i << ' ' << j << endl;
}
return 0;
}
Go
package main
import (
"bufio"
"os"
"strconv"
"strings"
)
func main() {
var n, m int
var x int64
reader := bufio.NewReader(os.Stdin)
line, _ := reader.ReadString('n')
params := strings.Fields(line)
n, _ = strconv.Atoi(params[0])
m, _ = strconv.Atoi(params[1])
x, _ = strconv.ParseInt(params[2], 10, 64)
a := make([]int64, n)
b := make([]int64, m)
line, _ = reader.ReadString('n')
nums := strings.Fields(line)
for i := 0; i < n; i {
a[i], _ = strconv.ParseInt(nums[i], 10, 64)
}
line, _ = reader.ReadString('n')
nums = strings.Fields(line)
for i := 0; i < m; i {
b[i], _ = strconv.ParseInt(nums[i], 10, 64)
}
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
for i, j := 0, m-1; i < n; i {
for j >= 0 && a[i] b[j] > x {
j--
}
if j >= 0 && a[i] b[j] == x {
writer.WriteString(strconv.Itoa(i) " " strconv.Itoa(j) "n")
return
}
}
}
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
var n, m int
var tmp, x int64
reader := bufio.NewReader(os.Stdin)
fmt.Fscanf(reader, "%d %d %dn", &n, &m, &x)
a := make(map[int64]int)
for i := 0; i < n; i {
fmt.Fscanf(reader, "%d", &tmp)
a[tmp] = i
}
fmt.Fscanf(reader, "n")
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
for j := 0; j < m; j {
fmt.Fscanf(reader, "%d", &tmp)
if value, ok := a[x-tmp]; ok {
fmt.Fprintf(writer, "%d %dn", value, j)
}
}
}
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
reader := bufio.NewReader(os.Stdin)
line, _ := reader.ReadString('n')
params := strings.Fields(line)
n, _ := strconv.Atoi(params[0])
m, _ := strconv.Atoi(params[1])
x, _ := strconv.ParseInt(params[2], 10, 64)
a := make(map[int64]int)
line, _ = reader.ReadString('n')
nums := strings.Fields(line)
for i := 0; i < n; i {
tmp, _ := strconv.ParseInt(nums[i], 10, 64)
a[tmp] = i
}
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
line, _ = reader.ReadString('n')
nums = strings.Fields(line)
for j := 0; j < m; j {
tmp, _ := strconv.ParseInt(nums[j], 10, 64)
if value, ok := a[x-tmp]; ok {
fmt.Fprintf(writer, "%d %dn", value, j)
}
}
}