题目链接

奥赛组队

题目描述

共有 名学生，每人有编程能力 和体育能力 。需要组建一支 人的编程队伍和一支 人的体育队伍，每人最多参加一队。目标是最大化两队的能力总和（编程队看 ，体育队看 ），并输出方案。

解题思路

这是一个复杂的组队优化问题，之前简单的贪心思路存在缺陷。一个正确且精妙的解法是采用“基准选择 + 迭代贪心优化”的策略。

算法思想：

  1. 建立基准选择：

    我们首先做一个最直接的贪心假设：编程队伍由编程能力最强的 名学生组成。我们以此为起点，计算一个初始的总分，并将这 名学生的状态标记为“编程队”。

  2. 准备迭代优化：

    接下来，我们需要为体育队挑选 名队员。我们进行 轮选择，每一轮都贪心地选择一个能使当前总分增长最大的操作。为了高效地做出选择，我们使用三个**最大堆（优先队列）**来动态维护候选人：

    • pq_b_unselected: 存储所有未入选学生的体育能力 。
    • pq_a_unselected: 存储所有未入选学生的编程能力 。
    • pq_b_minus_a_selected: 存储所有已在编程队的学生的“交换价值” 。

  3. 进行 s 轮贪心选择：

    循环 次，在每一轮中，我们比较两种决策能带来的收益：

    • 决策1（直接招募）：从 pq_b_unselected 堆顶取出体育能力最强的未入选学生 j。此操作的收益为 。
    • 决策2（交换队员）：这是一个组合操作。我们从 pq_b_minus_a_selected 堆顶取出“交换价值”最高的编程队员 k，再从 pq_a_unselected 堆顶取出编程能力最强的未入选学生 j 来补位。此操作的总收益为 。
    • 做出选择：比较两种决策的收益，选择收益更大的那个来执行。
    • 更新状态：执行选择后，更新总分，并修改相关学生的归属状态。例如，如果执行了决策2，学生 k 从编程队变为体育队，学生 j 从未入选变为编程队。同时，因为学生 j 现在是编程队员了，需要将他的“交换价值” 加入 pq_b_minus_a_selected 中，以备后续轮次选择。

  4. 清理无效堆顶：在每次从堆中取值前，需要检查堆顶的候选人状态是否仍然有效（例如，pq_b_unselected 的堆顶学生是否在之前的迭代中已经被选走了）。如果无效，则弹出，直到找到有效的堆顶。

这个迭代过程保证了每一步都做出了当前的最优增量选择，从而得到全局最优解。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct StudentValue {
    long long value;
    int id;

    bool operator<(const StudentValue& other) const {
        return value < other.value;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, p, s;
    cin >> n >> p >> s;

    vector<pair<long long, int>> a_sorted(n);
    vector<long long> a_val(n + 1), b_val(n + 1);
    for (int i = 0; i < n; ++i) {
        a_sorted[i].second = i + 1;
        cin >> a_sorted[i].first;
        a_val[i + 1] = a_sorted[i].first;
    }
    for (int i = 0; i < n; ++i) {
        cin >> b_val[i + 1];
    }

    sort(a_sorted.begin(), a_sorted.end(), greater<pair<long long, int>>());

    vector<int> op(n + 1, 0); // 0: unchosen, 1: programming, 2: sports
    long long total_score = 0;
    
    priority_queue<StudentValue> pq_a_unselected, pq_b_unselected, pq_b_minus_a_selected;

    for (int i = 0; i < p; ++i) {
        int stud_id = a_sorted[i].second;
        op[stud_id] = 1;
        total_score += a_sorted[i].first;
    }

    for (int i = 1; i <= n; ++i) {
        if (op[i] == 1) {
            pq_b_minus_a_selected.push({b_val[i] - a_val[i], i});
        } else {
            pq_a_unselected.push({a_val[i], i});
            pq_b_unselected.push({b_val[i], i});
        }
    }

    for (int i = 0; i < s; ++i) {
        long long gain1 = -2e18; // Recruit
        long long gain2 = -2e18; // Swap

        while (!pq_b_unselected.empty() && op[pq_b_unselected.top().id] != 0) {
            pq_b_unselected.pop();
        }
        if (!pq_b_unselected.empty()) {
            gain1 = pq_b_unselected.top().value;
        }

        while (!pq_b_minus_a_selected.empty() && op[pq_b_minus_a_selected.top().id] != 1) {
            pq_b_minus_a_selected.pop();
        }
        while (!pq_a_unselected.empty() && op[pq_a_unselected.top().id] != 0) {
            pq_a_unselected.pop();
        }

        if (!pq_b_minus_a_selected.empty() && !pq_a_unselected.empty()) {
            gain2 = pq_b_minus_a_selected.top().value + pq_a_unselected.top().value;
        }

        if (gain1 > gain2) {
            total_score += gain1;
            int stud_id = pq_b_unselected.top().id;
            op[stud_id] = 2;
            pq_b_unselected.pop();
        } else {
            total_score += gain2;
            int p_stud_id = pq_b_minus_a_selected.top().id;
            int u_stud_id = pq_a_unselected.top().id;
            pq_b_minus_a_selected.pop();
            pq_a_unselected.pop();
            
            op[p_stud_id] = 2;
            op[u_stud_id] = 1;
            
            pq_b_minus_a_selected.push({b_val[u_stud_id] - a_val[u_stud_id], u_stud_id});
        }
    }

    cout << total_score << endl;
    bool first = true;
    vector<int> p_team_final, s_team_final;
    for (int i = 1; i <= n; ++i) {
        if (op[i] == 1) p_team_final.push_back(i);
        if (op[i] == 2) s_team_final.push_back(i);
    }
    
    for (int i = 0; i < p_team_final.size(); ++i) {
        cout << p_team_final[i] << (i == p_team_final.size() - 1 ? "" : " ");
    }
    cout << endl;

    for (int i = 0; i < s_team_final.size(); ++i) {
        cout << s_team_final[i] << (i == s_team_final.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.*;

class StudentValue implements Comparable<StudentValue> {
    long value;
    int id;

    public StudentValue(long value, int id) {
        this.value = value;
        this.id = id;
    }

    @Override
    public int compareTo(StudentValue other) {
        return Long.compare(other.value, this.value); // Max-heap
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int p = sc.nextInt();
        int s = sc.nextInt();

        StudentValue[] a = new StudentValue[n];
        long[] a_val = new long[n + 1];
        long[] b_val = new long[n + 1];

        for (int i = 0; i < n; i++) {
            a[i] = new StudentValue(sc.nextLong(), i + 1);
            a_val[i + 1] = a[i].value;
        }
        for (int i = 0; i < n; i++) {
            b_val[i + 1] = sc.nextLong();
        }

        Arrays.sort(a);

        int[] op = new int[n + 1]; // 0: unchosen, 1: programming, 2: sports
        long totalScore = 0;

        PriorityQueue<StudentValue> pq_a_unselected = new PriorityQueue<>();
        PriorityQueue<StudentValue> pq_b_unselected = new PriorityQueue<>();
        PriorityQueue<StudentValue> pq_b_minus_a_selected = new PriorityQueue<>();

        for (int i = 0; i < p; i++) {
            op[a[i].id] = 1;
            totalScore += a[i].value;
        }

        for (int i = 1; i <= n; i++) {
            if (op[i] == 1) {
                pq_b_minus_a_selected.add(new StudentValue(b_val[i] - a_val[i], i));
            } else {
                pq_a_unselected.add(new StudentValue(a_val[i], i));
                pq_b_unselected.add(new StudentValue(b_val[i], i));
            }
        }

        for (int i = 0; i < s; i++) {
            long gain1 = Long.MIN_VALUE; // Recruit
            long gain2 = Long.MIN_VALUE; // Swap

            while (!pq_b_unselected.isEmpty() && op[pq_b_unselected.peek().id] != 0) {
                pq_b_unselected.poll();
            }
            if (!pq_b_unselected.isEmpty()) {
                gain1 = pq_b_unselected.peek().value;
            }

            while (!pq_b_minus_a_selected.isEmpty() && op[pq_b_minus_a_selected.peek().id] != 1) {
                pq_b_minus_a_selected.poll();
            }
            while (!pq_a_unselected.isEmpty() && op[pq_a_unselected.peek().id] != 0) {
                pq_a_unselected.poll();
            }

            if (!pq_b_minus_a_selected.isEmpty() && !pq_a_unselected.isEmpty()) {
                gain2 = pq_b_minus_a_selected.peek().value + pq_a_unselected.peek().value;
            }

            if (gain1 > gain2) {
                totalScore += gain1;
                StudentValue stud = pq_b_unselected.poll();
                op[stud.id] = 2;
            } else {
                totalScore += gain2;
                StudentValue p_stud = pq_b_minus_a_selected.poll();
                StudentValue u_stud = pq_a_unselected.poll();
                
                op[p_stud.id] = 2;
                op[u_stud.id] = 1;
                
                pq_b_minus_a_selected.add(new StudentValue(b_val[u_stud.id] - a_val[u_stud.id], u_stud.id));
            }
        }

        System.out.println(totalScore);
        
        List<Integer> pList = new ArrayList<>();
        List<Integer> sList = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            if(op[i] == 1) pList.add(i);
            if(op[i] == 2) sList.add(i);
        }
        Collections.sort(pList);
        Collections.sort(sList);

        StringJoiner pJoiner = new StringJoiner(" ");
        for (int id : pList) pJoiner.add(String.valueOf(id));
        System.out.println(pJoiner);

        StringJoiner sJoiner = new StringJoiner(" ");
        for (int id : sList) sJoiner.add(String.valueOf(id));
        System.out.println(sJoiner);
    }
}

import sys
import heapq

def main():
    n, p, s_count = map(int, sys.stdin.readline().split())
    a_list = list(map(int, sys.stdin.readline().split()))
    b_list = list(map(int, sys.stdin.readline().split()))

    students_a = []
    for i in range(n):
        students_a.append((-a_list[i], i + 1)) # Use negative for max-heap
    
    heapq.heapify(students_a)
    
    op = [0] * (n + 1) # 0: unchosen, 1: programming, 2: sports
    total_score = 0
    
    pq_a_unselected = []
    pq_b_unselected = []
    pq_b_minus_a_selected = []

    # Initial assignment to programming team
    for _ in range(p):
        a_val_neg, stud_id = heapq.heappop(students_a)
        op[stud_id] = 1
        total_score += -a_val_neg
    
    # Populate heaps
    for i in range(1, n + 1):
        if op[i] == 1:
            heapq.heappush(pq_b_minus_a_selected, (-(b_list[i-1] - a_list[i-1]), i))
        else:
            heapq.heappush(pq_a_unselected, (-a_list[i-1], i))
            heapq.heappush(pq_b_unselected, (-b_list[i-1], i))

    # Iteratively build sports team
    for _ in range(s_count):
        gain1 = -float('inf')
        gain2 = -float('inf')

        while pq_b_unselected and op[pq_b_unselected[0][1]] != 0:
            heapq.heappop(pq_b_unselected)
        if pq_b_unselected:
            gain1 = -pq_b_unselected[0][0]

        while pq_b_minus_a_selected and op[pq_b_minus_a_selected[0][1]] != 1:
            heapq.heappop(pq_b_minus_a_selected)
        while pq_a_unselected and op[pq_a_unselected[0][1]] != 0:
            heapq.heappop(pq_a_unselected)
            
        if pq_b_minus_a_selected and pq_a_unselected:
            gain2 = -pq_b_minus_a_selected[0][0] + -pq_a_unselected[0][0]

        if gain1 > gain2:
            total_score += gain1
            _, stud_id = heapq.heappop(pq_b_unselected)
            op[stud_id] = 2
        else:
            total_score += gain2
            _, p_stud_id = heapq.heappop(pq_b_minus_a_selected)
            _, u_stud_id = heapq.heappop(pq_a_unselected)
            
            op[p_stud_id] = 2
            op[u_stud_id] = 1
            
            heapq.heappush(pq_b_minus_a_selected, (-(b_list[u_stud_id-1] - a_list[u_stud_id-1]), u_stud_id))
            
    print(total_score)
    
    p_team = sorted([i for i, status in enumerate(op) if status == 1])
    s_team = sorted([i for i, status in enumerate(op) if status == 2])
    
    print(*p_team)
    print(*s_team)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 + 优先队列
  • 时间复杂度：。初始排序和建堆需要 ，但可以优化为 的 nth_element 和建堆。核心是 s 轮循环，每轮对数个堆进行操作，总复杂度为 。考虑到初始 p 个人的选择，整体复杂度可视为 。
  • 空间复杂度：，用于存储学生信息和优先队列。