题目链接

PEEK116 旺仔哥哥组战团

题目描述

共有 名士兵，每名士兵有战力 和人数上限要求 。若要将士兵 编入战团，则战团总人数不能超过 。需要组建一个战团，满足所有被选中士兵的人数上限要求，并使得总战力最大。

解题思路

这是一个贪心问题，可以通过排序和优先队列（小顶堆）来解决。

问题的核心约束是，一个战团的规模取决于团内人数上限要求最严格（即 最小）的士兵。这启发我们应从要求最宽松的士兵开始考虑。

具体解题步骤如下：

  1. 排序：将所有士兵按照人数上限 从大到小进行排序。如果 相同，可以按战力 从大到小排序（此为次要排序，不影响最终结果的正确性）。这种排序策略保证了我们在遍历过程中，当前士兵的人数上限 总是小于或等于之前所有已考虑士兵的人数上限。

  2. 使用优先队列（小顶堆）维护战团：我们按排序后的顺序遍历士兵，并使用一个小顶堆来维护当前已选入战团的士兵的战力。同时，我们维护 currentPowerSum（当前战团总战力）和 maxPower（所有可能战团中的最大总战力）。

  3. 遍历与动态调整：

    • 遍历排序后的每一个士兵 (p, s)。
    • 尝试加入：将该士兵的战力 p 加入小顶堆，并更新 currentPowerSum。
    • 检查并调整人数：此时，战团的人数（即小顶堆的大小）可能超过了当前士兵的人数上限 s。因为我们是按 降序遍历的，所以当前士兵的 s 是已考虑士兵中最小的上限，它构成了当前战团最严格的约束。
      • 如果 pq.size() > s，说明战团超员。为了使总战力最大化，我们应该移除战力最低的士兵。我们从小顶堆中弹出堆顶元素（即战力最低者），并从 currentPowerSum 中减去其战力，直到满足 pq.size() <= s。
    • 更新最大战力：每次调整后，当前的 currentPowerSum 就是一个满足约束的有效战团的总战力。我们用它来更新 maxPower。

  4. 最终结果：遍历结束后，maxPower 即为所求的答案。

代码

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

using namespace std;

struct Soldier {
    int p, s;
};

bool compareSoldiers(const Soldier& a, const Soldier& b) {
    if (a.s != b.s) {
        return a.s > b.s;
    }
    return a.p > b.p;
}

int main() {
    int n;
    cin >> n;
    vector<Soldier> soldiers(n);
    for (int i = 0; i < n; ++i) {
        cin >> soldiers[i].p >> soldiers[i].s;
    }

    sort(soldiers.begin(), soldiers.end(), compareSoldiers);

    priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
    long long currentPowerSum = 0;
    long long maxPower = 0;

    for (int i = 0; i < n; ++i) {
        pq.push(soldiers[i].p);
        currentPowerSum += soldiers[i].p;

        while (pq.size() > soldiers[i].s) {
            currentPowerSum -= pq.top();
            pq.pop();
        }
        
        maxPower = max(maxPower, currentPowerSum);
    }

    cout << maxPower << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;

class Soldier {
    int p, s;

    public Soldier(int p, int s) {
        this.p = p;
        this.s = s;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Soldier[] soldiers = new Soldier[n];
        for (int i = 0; i < n; i++) {
            soldiers[i] = new Soldier(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(soldiers, (a, b) -> {
            if (a.s != b.s) {
                return b.s - a.s;
            }
            return b.p - a.p;
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
        long currentPowerSum = 0;
        long maxPower = 0;

        for (int i = 0; i < n; i++) {
            pq.add(soldiers[i].p);
            currentPowerSum += soldiers[i].p;

            while (pq.size() > soldiers[i].s) {
                currentPowerSum -= pq.poll();
            }
            
            maxPower = Math.max(maxPower, currentPowerSum);
        }

        System.out.println(maxPower);
    }
}

import heapq

def main():
    n = int(input())
    soldiers = []
    for _ in range(n):
        soldiers.append(list(map(int, input().split())))

    # 按人数上限s降序，战力p降序排序
    soldiers.sort(key=lambda x: (-x[1], -x[0]))

    pq = []  # 小顶堆
    current_power_sum = 0
    max_power = 0

    for p, s in soldiers:
        heapq.heappush(pq, p)
        current_power_sum += p

        while len(pq) > s:
            current_power_sum -= heapq.heappop(pq)
            
        max_power = max(max_power, current_power_sum)

    print(max_power)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 + 优先队列（小顶堆）
  • 时间复杂度：，其中 是士兵的数量。排序需要 ，遍历士兵并对优先队列进行操作总共需要 。
  • 空间复杂度：，用于存储士兵信息和优先队列。