GESP C++ Level 5 Exam Questions (Greedy Algorithm Focus) luogu-B4071 [GESP202412 Level 5] Weapon Enhancement

**GESP Learning Resource List**
Exam Questions	Practice Questions	Syllabus Analysis
Level 1 Exam Questions List	Level 1 Practice Questions List	Level 1-5 Syllabus Analysis
Level 2 Exam Questions List	Level 2 Practice Questions List	Essential Skills for GESP/CSP Programming
Level 3 Exam Questions List	Level 3 Practice Questions List
Level 4 Exam Questions List	Level 4 Practice Questions List
Level 5 Exam Questions List	Level 5 Practice Questions List

**CSP Learning Resource List**
CSP-XL
2025 Liaoning CSP-XL Re-examination Questions Analysis

GESP C++ Level 5 exam questions for December 2024, focusing on greedy algorithms, involving enumeration and sorting, with a difficulty rating of ⭐⭐⭐☆☆, which is normal for level 5. Difficulty level on LuoguGeneral/Advanced−

luogu-B4071 [GESP202412 Level 5] Weapon Enhancement

Problem Requirements

Problem Description

Little Yang has types of weapons and types of enhancement materials. The type of enhancement material is compatible with the type of weapon, and Little Yang can spend coins to modify the corresponding weapon to any weapon.

Little Yang’s favorite weapon is the type, so he hopes that the number of enhancement materials compatible with this weapon is strictly greater than that of other weapons. Please help Little Yang calculate the minimum cost in coins required to meet this condition.

Input Format

The first line contains two positive integers , meaning as described in the problem statement.

Then lines follow, each containing two positive integers , representing the compatible weapon for the type of enhancement material and the modification cost.

Output Format

Output a single integer, representing the minimum cost in coins required to ensure that the number of enhancement materials compatible with the type of weapon is strictly greater than that of other weapons.

Input/Output Example #1

Input #1

Output #1

Explanation/Hint

Example Explanation

Spend to change the compatible weapon of the third enhancement material from to . At this point, weapon has types of enhancement materials compatible, while weapons and each have types of enhancement materials compatible, satisfying the condition that the number of enhancement materials compatible with the type of weapon is strictly greater than that of other weapons.

Data Range

For data, it is guaranteed that , and .

Subtask ID	Score Proportion

Problem Analysis

Solution Approach

Solution Approach

The core goal of this problem is to ensure that the number of enhancement materials for the type of weapon is strictly greater than that of any other weapon, i.e., for any , it holds that . At the same time, the total cost must be minimized.

This is a typical enumeration + greedy problem. Since the range of is relatively small (), we can enumerate the possible number of enhancement materials that the type of weapon will ultimately have.

For a specific target number :

Condition 1: The number of enhancement materials for the type of weapon must reach .
Condition 2: The number of materials for all other weapons must be strictly less than (i.e., at most ).

To satisfy the above conditions while minimizing costs, we adopt the following greedy strategy:

Forced Reduction: For each weapon other than the type, if its current number of materials is , it must be reduced to . To minimize costs, we prioritize removing the materials with the lowest modification costs from that weapon and change them to the type of weapon. Record this cost and the increase in the number of the type of weapon.
Supplementing Quantity: After step 1, if the number of materials for the type of weapon is still insufficient, we need to select the cheapest available materials from all remaining materials (including those not forcibly removed) to change to the type of weapon until the number reaches .

We enumerate the process of , calculating the total cost for each case, and take the minimum value as the answer.

Algorithm Steps

Read input, and .
Count the initial number of materials for the type of weapon cnt1.
Store the modification costs for the materials corresponding to other weapons in their respective lists materials[p], and sort each list in ascending order for subsequent greedy selection.
Enumerate the final number of materials for the type of weapon (from cnt1 to ):

Initialize current cost cur_cost = 0, and the current number of materials to be moved to the type of weapon total_movecount = 0.
Create a candidate pool pool to store the costs of materials that are not “forced modifications”.
Iterate through each weapon ():

Calculate the number of materials that weapon needs to remove move = materials[j].size() - (i - 1).
If move > 0, then accumulate the costs of the first move minimum costs from materials[j] into cur_cost, and increment total_movecount by move. The remaining elements are placed in pool.
If move <= 0, then place all elements of materials[j] into pool.

Check if the current number of materials for the type of weapon cnt1 + total_movecount meets .
If not, calculate the gap need = i - (cnt1 + total_movecount). Sort the pool and accumulate the costs of the first need minimum costs into cur_cost.
Update the global minimum cost total_cost.

5. Output total_cost。

Complexity

Time Complexity: The outer loop enumerates at most times. The inner loop iterates through weapons, collects elements into pool, and sorts pool. The total time complexity is approximately . Given the data range of , the computational load is about level, which can be handled.
Space Complexity: The space complexity is due to the need to store the costs of all materials.

Example Code

The complete code implementation is as follows：

#include &lt;algorithm&gt;#include &lt;climits&gt;#include &lt;iostream&gt;#include &lt;vector&gt;int main() {    // n: Number of weapon types, m: Total number of enhancement materials    int n, m;    std::cin &gt;&gt; n &gt;&gt; m;
    // materials[p] stores the modification costs for various enhancement materials compatible with weapon p    // Using vector for subsequent sorting and processing    std::vector&lt;std::vector&lt;int&gt;&gt; materials(n + 1);    int cnt1 = 0; // Record the initial number of materials compatible with weapon type 1    for (int i = 0; i &lt; m; i++) {        int p, c;        std::cin &gt;&gt; p &gt;&gt; c;        if (p == 1) {            // If it is already a material for weapon type 1, count directly without cost            cnt1++;        } else {            // Otherwise, record the cost to modify this material to be compatible with weapon type 1            materials[p].push_back(c);        }    }    // For each weapon other than type 1, sort its materials by modification cost in ascending order    // This way, when we need to reduce the number of materials for that weapon, we can prioritize removing the cheapest ones    for (int i = 2; i &lt;= n; i++) {        std::sort(materials[i].begin(), materials[i].end());    }    long long total_cost = LLONG_MAX; // Initialize the minimum total cost to the maximum value    // Enumerate the final number of materials for weapon type 1 i    // The range of i: from the current cnt1 to all materials belonging to it (m)    // The goal is: weapon type 1 has i materials, and all other weapons have less than i (i.e., at most i-1)    for (int i = cnt1; i &lt;= m; i++) {        std::vector&lt;int&gt; pool; // Candidate pool: stores those materials that do not need to be forcibly bought (to suppress others' counts), but can be used to increase the count for weapon type 1        int total_movecount = 0; // Record the number of materials that must be modified to “suppress” other weapons        long long cur_cost = 0;  // Total cost for the current scheme        // Iterate through all weapons (materials actually start from index 2, 0 and 1 are empty or already processed)        for (int j = 0; j &lt; materials.size(); j++) {            // Calculate how many materials weapon j needs to remove to make its count strictly less than i            // Original count size, target remaining count &lt;= i-1            // Number to remove = size - (i - 1) = size - i + 1            // Code logic: move = size - i, then remove elements from index 0 to move (a total of move + 1)            // Remaining: size - (size - i + 1) = i - 1, satisfying the condition            int move = materials[j].size() - i;            for (int k = 0; k &lt; materials[j].size(); k++) {                if (k &lt;= move) {                    // Must modify materials (to make this weapon's material count &lt; i)                    cur_cost += materials[j][k];                    total_movecount++;                } else {                    // Materials that do not need to be forcibly modified, put into candidate pool                    // If later the count for weapon type 1 is still insufficient, we can pick from here for cheap ones                    pool.push_back(materials[j][k]);                }            }        }        // Count the current number of materials for weapon type 1: initial cnt1 + forced modifications total_movecount        // If still not reaching target count i, need to supplement from candidate pool        if (cnt1 + total_movecount &lt; i) {            // Sort the candidate pool by cost            std::sort(pool.begin(), pool.end());            // Greedily select the cheapest few to supplement until reaching count i            for (int j = 0; j &lt; i - total_movecount - cnt1; j++) {                cur_cost += pool[j];            }        }        // Update global minimum cost        total_cost = std::min(total_cost, cur_cost);    }    std::cout &lt;&lt; total_cost;    return 0;}

【Recommended】 Mobile Version Recommended:【GESP】 C++ Certification Learning Resource Summary

【Recommended】 Desktop Version Recommended: GESP/CSP Exam Material Website:https://wiki.coderli.com/ Dictionary-style resource organization, easy and quick to browse by category.