0002-整数对最小和

题目描述

给定两个整数数组 array1 array2
数组元素按升序排列
假设从array1 array2中分别取出一个元素可构成一对元素
现在需要取出K个元素
并对取出的所有元素求和
计算和的最小值
注意：
两对元素如果对应于array1 array2中的两个下标均相同，则视为同一个元素

输入描述

输入两行数组array1 array2
每行首个数字为数组大小 size( 0 < size <= 100)
array1，array2中的每个元素e， 0< e <1000
接下来一行为正整数k (0 < k <= array1.size() * array2.size())

输出描述

满足要求的最小和

示例一

输入

3 1 1 2
3 1 2 3
2
1
2
3

输出

4
1

说明

用例中，需要取两个元素 取第一个数组第0个元素 与第二个数组第0个元素，组成一对元素[1,1]
取第一个数组第1个元素 与第二个数组第0个元素，组成一对元素[1,1]
求和为1+1+1+1=4 为满足要求的最小和

思路解析和复杂度分析

思路解析

这道题可以看做是两个有序数组的归并排序的变形。先将两个数组中的元素两两相加，得到 m×n 个元素，将这些元素按和的大小升序排序。题目要求取出前 k 个元素的和的最小值。
因为数组是有序的，可以考虑使用双指针法，用两个指针 i 和 j 分别指向数组 A 和数组 B，从头开始依次枚举每个元素，记录当前已经选取的元素个数 cnt。每次选取两个指针指向的元素中较小的一个，将其加入答案中，并将所在数组的指针向后移动一位。当 cnt 达到 k 时停止。

复杂度分析

排序的时间复杂度为O(mn log(mn))，枚举的时间复杂度为 O(k)，因此总时间复杂度为 O(mn log(mn)+k)。当 k 远小于 m×n 时，算法的时间复杂度较低，但当 k 接近 m×n 时，算法效率较低。
空间复杂度为 O(mn)，因为需要开辟一个数组来存储每个元素的和以及对应的下标。

参考解题

参考解题 C

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int i;
    int j;
    int val;
} Node;

int cmp (const void *a, const void *b) {
    return ((Node *)a)->val - ((Node *)b)->val;
}

int main () {
    int m, n, k;
    scanf("%d", &m);
    int *arr1 = (int *) malloc (sizeof(int) * m);
    for (int i = 0; i < m; i++) {
        scanf("%d", arr1 + i);
    }
    scanf("%d", &n);
    int *arr2 = (int *) malloc (sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr2 + i);
    }
    scanf("%d", &k);

    Node *nodes = (Node *) malloc (sizeof(Node) * m * n);
    int nodesLen = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            nodes[nodesLen].i = i;
            nodes[nodesLen].j = j;
            nodes[nodesLen].val = arr1[i] + arr2[j];
            nodesLen++;
        }
    }

    qsort(nodes, nodesLen, sizeof(Node), cmp);

    int ans = 0;
    int used[m];
    for (int i = 0; i < m; i++) {
        used[i] = 0;
    }
    int cnt = 0;
    for (int i = 0; i < nodesLen; i++) {
        if (used[nodes[i].i]) continue;
        ans += nodes[i].val;
        used[nodes[i].i] = 1;
        cnt++;
        if (cnt == k) break;
    }

    printf("%d\\n", ans);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

参考解题 C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int i, j, val;
};

bool cmp(Node a, Node b) {
    return a.val < b.val;
}

int main() {
    int m, n, k;
    cin >> m;
    vector<int> arr1(m);
    for (int i = 0; i < m; i++) {
        cin >> arr1[i];
    }
    cin >> n;
    vector<int> arr2(n);
    for (int i = 0; i < n; i++) {
        cin >> arr2[i];
    }
    cin >> k;

    vector<Node> nodes(m * n);
    int nodesLen = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            nodes[nodesLen].i = i;
            nodes[nodesLen].j = j;
            nodes[nodesLen].val = arr1[i] + arr2[j];
            nodesLen++;
        }
    }

    sort(nodes.begin(), nodes.end(), cmp);

    int ans = 0;
    vector<bool> used(m, false);
    int cnt = 0;
    for (int i = 0; i < nodesLen; i++) {
        if (used[nodes[i].i]) continue;
        ans += nodes[i].val;
        used[nodes[i].i] = true;
        cnt++;
        if (cnt == k) break;
    }

    cout << ans << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

参考解题 Java（1）

import java.util.*;

public class Main {
    static class Node {
        int i, j, val;
        public Node (int i, int j, int val) {
            this.i = i;
            this.j = j;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] arr1 = new int[m];
        for (int i = 0; i < m; i++) {
            arr1[i] = sc.nextInt();
        }
        int n = sc.nextInt();
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++) {
            arr2[i] = sc.nextInt();
        }
        int k = sc.nextInt();

        Node[] nodes = new Node[m * n];
        int nodesLen = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                nodes[nodesLen++] = new Node(i, j, arr1[i] + arr2[j]);
            }
        }

        Arrays.sort(nodes, new Comparator<Node>() {
            public int compare(Node a, Node b) {
                return a.val - b.val;
            }
        });

        int ans = 0;
        boolean[] used = new boolean[m];
        int cnt = 0;
        for (int i = 0; i < nodesLen; i++) {
            if (used[nodes[i].i]) continue;
            ans += nodes[i].val;
            used[nodes[i].i] = true;
            cnt++;
            if (cnt == k) break;
        }

        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

参考解题 Java（2）

public static void main(String[] args) {
    //int[] a = {1, 1, 2};
    //int[] b = {1, 2, 3};
    //int k = 2;
    Scanner sc = new Scanner(System.in);
    String strA = sc.nextLine();
    String strB = sc.nextLine();
    int k = sc.nextInt();
    
    String[] a = strA.substring(1).trim().split(" ");
    String[] b = strB.substring(1).trim().split(" ");
    
    ArrayList<Integer> list = new ArrayList<Integer>(k);
    for (String i : a) {
        for (String j : b) {
            list.add(Integer.parseInt(i) + Integer.parseInt(j));
        }
    }
    Collections.sort(list, (a1, a2) -> a1.compareTo(a2));//升序排列
    int s = 0;
    for (int i = 0; i < k; i++) {
        s += list.get(i);
    }
    System.out.println(s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

参考解题 Python

m, *a = map(int, input().split())
n, *b = map(int, input().split())
k = int(input())

nodes = []
for i in range(m):
    for j in range(n):
        nodes.append((i, j, a[i] + b[j]))
nodes.sort(key=lambda x: x[2])

ans = 0
used = [False] * m
cnt = 0
for i, j, val in nodes:
    if used[i]:
        continue
    ans += val
    used[i] = True
    cnt += 1
    if cnt == k:
        break

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

参考解题 JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on('line', (line) => {
  const inputs = line.split(' ').map(Number);
  if (inputs.length === 1) {
    return;
  }

  const m = inputs[0];
  const a = inputs.slice(1, m + 1);
  const n = inputs[m + 1];
  const b = inputs.slice(m + 2, m + n + 2);
  const k = inputs[m + n + 2];

  const nodes = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      nodes.push([i, j, a[i] + b[j]]);
    }
  }

  nodes.sort((a, b) => a[2] - b[2]);

  let ans = 0;
  const used = new Array(m).fill(false);
  let cnt = 0;
  for (let i = 0; i < nodes.length; i++) {
    const [index, , val] = nodes[i];
    if (used[index]) {
      continue;
    }
    ans += val;
    used[index] = true;
    cnt++;
    if (cnt === k) {
      break;
    }
  }

  console.log(ans);
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

参考解题 Go

package main

import (
    "fmt"
    "sort"
)

func main() {
    var m, n, k int
    fmt.Scan(&m)
    a := make([]int, m)
    for i := 0; i < m; i++ {
        fmt.Scan(&a[i])
    }
    fmt.Scan(&n)
    b := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&b[i])
    }
    fmt.Scan(&k)

    type Node struct {
        i, j, val int
    }

    nodes := make([]Node, 0, m*n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            nodes = append(nodes, Node{i, j, a[i] + b[j]})
        }
    }

    sort.Slice(nodes, func(i, j int) bool {
        return nodes[i].val < nodes[j].val
    })

    ans := 0
    used := make([]bool, m)
    cnt := 0
    for i := 0; i < len(nodes); i++ {
        if used[nodes[i].i] {
            continue
        }
        ans += nodes[i].val
        used[nodes[i].i] = true
        cnt++
        if cnt == k {
            break
        }
    }

    fmt.Println(ans)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53