题面描述:

塔子哥在进行计网实验后，又收到了一周的接口板需求。他需要为两台设备配置接口板，使得每台设备的接口板转发能力之和恰好等于设备的整机转发能力。输入包括目标设备的转发能力、客户订购的接口板数量以及接口板的转发能力列表。若能够满足条件，输出两台设备配置的接口板转发能力列表（需按从小到大排列）；若无法满足，则输出-1。

思路

由于题目保证如果存在解，那么解一定是唯一的，所以接口板容量之和肯定是整机转发能力的两倍。

我们可以使用动态规划来解决这个问题，设f[i][j]表示前i个接口板能否组成转发能力为j的整机，如果能组成，那么f[i][j]定义为i表示第i个元素为结尾接口板，那么我们有状态转移方程：

f[i][j] = f[i - 1][j] or f[i - 1][j - a[i]]

其中a[i]表示第i个接口板的容量。由于需要记录路径，我们可以使用pre[i][j]来记录f[i][j]的上一个状态。

pre[i][j] = f[i - 1][j - a[i]]

由于每次只需要前一个状态，所以我们可以使用一维的f来进行优化。

最后将符合条件的路径找出，将其分成两部分，分别排序，然后对比输出即可。

题解

为了给两台设备配置接口板，使得每台设备的接口板转发能力之和恰好等于设备的整机转发能力，我们可以利用动态规划来解决这个问题。具体思路如下：

1. 问题分析：

   • 输入中给定的目标设备的转发能力为 $m$，并且客户订购了 $n$ 块接口板。根据题目的描述，如果存在解，那么所有接口板的容量之和必定等于 $2m$（即两台设备的转发能力总和）。因此，如果这些接口板的总和不等于 $2m$，直接输出 -1。

2. 动态规划状态定义：

   • 我们定义 f[i][j] 表示前 $i$ 个接口板能否组成转发能力为 $j$ 的整机。如果能组成，那么 f[i][j] 的值为真。我们还需要使用 pre[i][j] 来记录路径，表示 f[i][j] 的上一个状态。

3. 状态转移方程：

   • 状态转移方程为： $f[i][j] = f[i - 1][j] \text{ or }$$f[i - 1][j - a[i]]$
   • 其中，$a[i]$ 表示第 $i$ 个接口板的容量。

4. 优化：

   • 由于我们只需要使用前一个状态，因此可以将 f 数组优化为一维数组，从而减少空间复杂度。

5. 路径回溯：

   • 一旦找到能够组成转发能力为 $m$ 的方案，我们需要回溯找到所用的接口板。利用 pre 数组可以帮助我们记录并找出使用了哪些接口板。

6. 结果输出：

   • 将找到的两部分接口板分别排序，然后进行比较，按照题目要求的顺序输出。

代码

Python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    m = int(data[0])  # 读取 m
    n = int(data[1])  # 读取 n
    a = list(map(int, data[2:2 + n]))  # 读取数组 a

    # 如果数组元素的总和不等于 2m，则输出 -1 并退出
    if sum(a) != m * 2:
        print(-1)
        return

    # 初始化前驱数组 pre 和动态规划数组 f
    pre = [[-1] * (m + 1) for _ in range(n)]
    f = [-1] * (m + 1)
    f[0] = 0

    # 动态规划过程
    for i in range(n):
        for j in range(m, a[i] - 1, -1):
            if f[j - a[i]] != -1:
                pre[i][j] = f[j - a[i]]
                f[j] = i

    # 如果能找到一个和为 m 的子集
    if f[m] != -1:
        vis = [False] * n
        i, j = m, f[m]
        while i > 0:
            vis[j] = True
            k = a[j]
            j = pre[j][i]
            i -= k

        ans1, ans2 = [], []
        for i in range(n):
            if vis[i]:
                ans1.append(a[i])
            else:
                ans2.append(a[i])

        # 对两个子集进行排序
        ans1.sort()
        ans2.sort()

        # 比较两个子集，确保 ans1 是字典序较小的
        if ans1[0] > ans2[0] or (ans1[0] == ans2[0] and len(ans1) < len(ans2)):
            ans1, ans2 = ans2, ans1

        # 输出两个子集
        print(" ".join(map(str, ans1)))
        print(" ".join(map(str, ans2)))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();  // 读取输入的数组元素
        }

        // 如果数组元素的总和不等于 2m，则输出 -1 并退出
        if (Arrays.stream(a).sum() != m * 2) {
            System.out.println(-1);
            return;
        }

        // 初始化前驱数组 pre 和动态规划数组 f
        int[][] pre = new int[n][m + 1];
        for (int[] row : pre) Arrays.fill(row, -1);
        int[] f = new int[m + 1];
        Arrays.fill(f, -1);
        f[0] = 0;

        // 动态规划过程
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= a[i]; --j) {
                if (f[j - a[i]] != -1) {
                    pre[i][j] = f[j - a[i]];
                    f[j] = i;
                }
            }
        }

        // 如果能找到一个和为 m 的子集
        if (f[m] != -1) {
            boolean[] vis = new boolean[n];
            for (int i = m, j = f[m]; i > 0;) {
                vis[j] = true;
                int k = a[j];
                j = pre[j][i];
                i -= k;
            }

            List<Integer> ans1 = new ArrayList<>();
            List<Integer> ans2 = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                if (vis[i]) ans1.add(a[i]);
                else ans2.add(a[i]);
            }

            // 对两个子集进行排序
            Collections.sort(ans1);
            Collections.sort(ans2);

            // 比较两个子集，确保 ans1 是字典序较小的
            if (ans1.get(0) > ans2.get(0) || 
                (ans1.get(0).equals(ans2.get(0)) && ans1.size() < ans2.size())) {
                List<Integer> temp = ans1;
                ans1 = ans2;
                ans2 = temp;
            }

            // 输出两个子集
            for (int i = 0; i < ans1.size(); ++i) 
                System.out.print(ans1.get(i) + (i == ans1.size() - 1 ? "\n" : " "));
            for (int i = 0; i < ans2.size(); ++i) 
                System.out.print(ans2.get(i) + (i == ans2.size() - 1 ? "\n" : " "));
        }
    }
}

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> m >> n;
    vector<int> a(n);
    for (int i = 0;i < n;++ i) cin >> a[i];
    if (accumulate(a.begin(), a.end(), 0) != m * 2) {
    cout << -1 << endl;
    return 0;
    }
    vector<vector<int>> pre(n, vector<int> (m + 1, -1));
    vector<int> f(m + 1, -1);
    f[0] = 0;
    for (int i = 0;i < n;++ i) {
        for (int j = m;j >= a[i];-- j) if (~f[j - a[i]]) {
            pre[i][j] = f[j - a[i]];
            f[j] = i;
        }
    }
    if (~f[m]) {
        vector<bool> vis(n, false);
        for (int i = m, j = f[m];i > 0;) {
            vis[j] = true;
            int k = a[j];
            j = pre[j][i];
            i -= k;
        }
        vector<int> ans1, ans2;
        for (int i = 0;i < n;++ i) {
            if (vis[i]) ans1.push_back(a[i]);
            else ans2.push_back(a[i]);
        }
        sort(ans1.begin(), ans1.end());
        sort(ans2.begin(), ans2.end());
        if (ans1[0] > ans2[0] || (ans1[0] == ans2[0] && ans1.size() < ans2.size())) swap(ans1, ans2);
        for (int i = 0;i < ans1.size();++ i) cout << ans1[i] << " \n"[i == ans1.size() - 1];
        for (int i = 0;i < ans2.size();++ i) cout << ans2[i] << " \n"[i == ans2.size() - 1];
    }
    return 0;
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function () {
    let m = parseInt(await readline()); // 读取 m
    let n = parseInt(await readline()); // 读取 n
    let a = (await readline()).split(" ").map(Number); // 读取数组 a

    let sumA = a.reduce((sum, x) => sum + x, 0);
    if (sumA !== 2 * m) {
        console.log(-1);
        rl.close();
        return;
    }

    let pre = Array.from({ length: n }, () => Array(m + 1).fill(-1));
    let f = Array(m + 1).fill(-1);
    f[0] = 0;

    for (let i = 0; i < n; i++) {
        for (let j = m; j >= a[i]; j--) {
            if (f[j - a[i]] !== -1 && f[j] === -1) {
                pre[i][j] = f[j - a[i]];
                f[j] = i;
            }
        }
    }

    if (f[m] === -1) {
        console.log(-1);
        rl.close();
        return;
    }

    let vis = Array(n).fill(false);
    for (let i = m, j = f[m]; i > 0 && j !== -1;) {
        vis[j] = true;
        let k = a[j];
        j = pre[j][i];
        i -= k;
    }

    let ans1 = [], ans2 = [];
    for (let i = 0; i < n; i++) {
        if (vis[i]) ans1.push(a[i]);
        else ans2.push(a[i]);
    }

    ans1.sort((x, y) => x - y);
    ans2.sort((x, y) => x - y);

    if (
        ans1.length > 0 && ans2.length > 0 &&
        (ans1[0] > ans2[0] || (ans1[0] === ans2[0] && ans1.length < ans2.length))
    ) {
        [ans1, ans2] = [ans2, ans1];
    }

    console.log(ans1.join(" "));
    console.log(ans2.join(" "));

    rl.close();
})();

题目描述

$\qquad$小明做完了上周的计网实验，但是按照一周一个的原则，他又收到了这周的份额，holy damn！

$\qquad$柜式路由器需要配备接口板才可以工作,接口板用于接入用户业务，且接口板转发能力的和不能大于路由器整机的转发能力。当前某客户订购了2台设备和num块接口板。请计算是否存在一种安装方法，使用户选购的接口板，刚好能装到两台设备上，且每台设备配置的口板的转发能力之和,刚好和整机的转发能力相等。

$\qquad$ 1、设备整机转发能力的单位是Gbps,Gbps是设备单位时间内传输的比特数，代表千兆比特/秒。为了简化问题,规定值为整数,范围为[1,2000]。

$\qquad$ 2、客户订购的接口板数量num,值的范围[1,200]。

$\qquad$ 3、接口板容量的单位也是Gbps，比如1010 40 40 100，代表选购了5块接口板,转发能力分别是10Gbps, 10Gbps, 40Gbps, 40Gbps, 100Gbps，接口板转发能力的范围一般为特定枚举值，为了简化问题，规定值为正整数。

输入描述

$\qquad$第一行是目标设备的转发能力。第二行是客户订购的接口板数量num 。第三行是订购的包含num个接口板的转发能力的列表。

输出描述

$\qquad$如果存在满足要求的安装方法，请分两行输出两台设备配置的接口板的转发能力的列表，且要求每台设备的单板，按转发能力从小到大排列。两台设备的单板，第一个单板转发能力小的优先输出。如果第一个单板转发能力相同，那单板数多的优先输出。如果不存在对应的安装方案，则返回-1。用例保证在满足前面条件的情况下，不会有多种不同的结果。

样例一

输入

100
5
40 10 10 40 100

输出

10 10 40 40
100

样例二

输入

100
3
10 10 20

输出

-1