思路：01背包求具体方案

本题改编自1049. 最后一块石头的重量 II - 力扣（LeetCode）

在原题的基础上增加了对具体对战斗方案的求解

在战斗过程中，我们需要记录下每一场战斗的结果，包括哪两个角斗士进行了战斗，以及他们的战斗结果。这个记录将作为我们的输出。

最后，我们将所有的战斗结果输出，这就是我们的决斗方案。

时间复杂度

$O(nm)$

代码

C++

#include <iostream>
#include <numeric>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using namespace std;
using vec = vector<int>;
using vv = vector<vector<int>>;

int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    int sum = accumulate(arr.begin(), arr.end(), 0);
    vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
    vector<vv> path(n + 1, vv(sum + 1));
    int ans = sum, x = 0, y = 0;
    dp[0][0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= sum; ++j) {
            if (dp[i - 1][j]) {
                path[i][j] = path[i - 1][j];
                dp[i][j] = dp[i - 1][j];
            } else if (j >= arr[i - 1]){
                dp[i][j] = dp[i][j] | dp[i - 1][j - arr[i - 1]];
                path[i][j] = path[i - 1][j - arr[i - 1]];
                if (dp[i][j]) {
                    int c = abs(sum - 2 * j);
                    path[i][j].push_back(i - 1);
                    if (c < ans) {
                        ans = c;
                        x = i; y = j;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    vector<int> a = path[x][y], b;
    set<int> st(a.begin(), a.end());
    for (int i = 0; i < n; ++i) if (!st.count(i)) b.push_back(i);
    vector<vector<int>> plan;
    for (size_t i = 0, j = 0; i < a.size() && j < b.size(); ) {
        int x = a[i], y = b[j];
        int vx = arr[x], vy = arr[y];
        plan.push_back({x + 1, y + 1});
        if (vx == vy) {
            ++i; ++j;
        } else if (vx < vy) {
            arr[y] -= arr[x];
            ++i;
        } else {
            arr[x] -= arr[y];
            ++j;
        }
    }
    cout << plan.size() << endl;
    for (auto e : plan) {
        cout << e[0] << " " << e[1] << endl;
    }
}

python代码

n = int(input())
power = list(map(int, input().split()))
half = sum(power) // 2

dp = [[0] * (half + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    for tar in range(half + 1):
        dp[i+1][tar] = dp[i][tar]
        if power[i] <= tar:
            dp[i+1][tar] |= dp[i][tar - power[i]]

p1 = []
for tar in range(half, -1, -1):
    if dp[-1][tar] == 1:
        break
print(sum(power) - tar * 2)        
i = n - 1
while tar > 0:
    if tar >= power[i] and dp[i][tar-power[i]] == 1:
        p1.append(i)
        tar -= power[i]
    i -= 1
p1_set = set(p1)
p2 = [i for i in range(n) if i not in p1_set]
k = 0
ans = []
while p1 and p2:
    k += 1
    ans.append((p1[-1], p2[-1]))
    x = min(power[p1[-1]], power[p2[-1]])
    res_p1 = power[p1[-1]] - x
    res_p2 = power[p2[-1]] - x

    if res_p1 == 0:
        p1.pop()
    else:
        power[p1[-1]] = res_p1  

    if res_p2 == 0:
        p2.pop()
    else:
        power[p2[-1]] = res_p2    
print(k)
for x, y in ans:
    print("{} {}".format(x+1, y+1))

Java代码

import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        int n = sc.nextInt();
        int[] people = new int[n];
        int sum = 0;
        for (int i=0;i<n;i++)
        {
            people[i] = sc.nextInt();
            sum+=people[i];
        }
        //容量为i的背包需要的人的下标
        int target = sum/2;
        Set[] conts = new Set[target+1];
        for (int j=0;j<conts.length;j++)
            conts[j] = new HashSet<Integer>();
        int[] dp = new int[target+1];
        for(int i=0;i<people.length;i++)
        {
            for(int j=target;j>=people[i];j--)
            {
                int cur = dp[j-people[i]]+people[i];
                if(dp[j]>cur)
                {//不变

                }
                else{
                    conts[j] = new HashSet<Integer>(conts[j-people[i]]);
                    conts[j].add(i);//加入当前的斗士
                    dp[j] = cur;
                }
            }
        }
        //模拟决斗方案
        System.out.println(sum-2*dp[target]);
        Deque<Integer> t1 = new ArrayDeque<>(conts[target]);//第一队下标
        Deque<Integer> t2 = new ArrayDeque<>();//第一队下标
        for (int i=0;i<people.length;i++)
            if(!conts[target].contains(i))
                t2.offer(i);
        int k=0;
        List<int[]> ans = new ArrayList<>();
        while (!t1.isEmpty()&&!t2.isEmpty())
        {
            //第一队
            int a = t1.poll();
            //第二队
            int b = t2.poll();
            ans.add(new int[]{a+1,b+1});
            if(people[a]>people[b])
            {
                people[a] = people[a]-people[b];
                t1.offer(a);
            }
            else if(people[a]<people[b])
            {
                people[b] = people[b]-people[a];
                t2.offer(b);
            }
            k++;
        }
        System.out.println(k);
        for(int i=0;i<ans.size();i++)
            System.out.println(ans.get(i)[0]+" "+ans.get(i)[1]);
    }
}

题目描述

小红从父辈那里继承了一座角斗场以及$n$个角斗士，每个角斗士的战力为$a_i(1\le i\le n)$。

但是小红讨厌角斗场，所以他安排了最后的决斗，让角斗士一对一战斗。当然，战力高的角斗士会取得胜利，但是经过战斗的他，战斗力会变为$|a_i-a_j|$，而另一个角斗士则会死亡。

小红希望尽可能让最后的角斗士战力最小，当然，如果所有角斗士都死亡了会更好。

小红找到了你，希望你能帮他设计一个决斗的方案。

输入描述

第一行输入两个正整数$n$，代表角斗士的数量。

第二行输入$n$个正整数$a_i$，代表每个角斗士的战力

$1\le n,a_i\le 100$

输出描述

第一行输出一个整数$h$，代表最后的角斗士的战力。

第二行输出一个正整数$k$，代表总共的决斗次数。

接下来$k$行，每行输出你安排的一场决斗方案。

样例

输入

4
1 2 3 4

输出

0
3
1 2
3 4
2 4