GESP C++ Level 4 Real Questions (Sorting, Prefix Sum, Sliding Window) [202406] Treasure Box (luogu-B4006)

GESP C++ Level 4 real questions for June 2024. This problem mainly tests the concepts of sorting, prefix sums, and sliding windows. The brute force difficulty is not high, but the sliding window requires some thought, with an overall difficulty rating of ⭐⭐★☆☆. This problem is rated as <span>Popular-</span>.

GESP Level 1 Practice Questions List
GESP Level 1 Real Questions List
GESP Level 2 Practice Questions List
GESP Level 2 Real Questions List
GESP Level 3 Practice Questions List
GESP Level 3 Real Questions List
GESP Level 4 Practice Questions List
GESP Level 4 Real Questions List
GESP Level 1-5 Syllabus Analysis

luogu-B4006 [GESP202406 Level 4] Treasure Box

Problem Requirements

Problem Description

Little Yang discovered treasure boxes, where the value of the th treasure box is .

Little Yang can choose some treasure boxes to put into his backpack and take away, but Little Yang’s backpack is quite special. Assuming the maximum value of the selected treasure boxes is and the minimum value is , Little Yang needs to ensure that , otherwise, his backpack will be damaged.

Little Yang wants to know the maximum total value of the treasure boxes he can take without damaging his backpack.

Input Format

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

The second line contains positive integers , representing the values of the treasure boxes.

Output Format

Output an integer representing the maximum total value of the treasure boxes that can be taken away.

Input and Output Examples #1

Input #1

5 1
1 2 3 1 2

Output #1

Explanation/Hint

[Sample Explanation]:

Without damaging the backpack, Little Yang can take two treasure boxes worth and one treasure box worth .

[Data Range]:

For all data, it is guaranteed that ,,.

Problem Analysis

This problem can be solved using two approaches:

Method 1: Prefix Sum Method

First, sort all treasure box values to ensure that the difference between the maximum and minimum values is continuous.
Preprocess the prefix sum array for quick calculation of the total value of any range of treasure boxes.
Enumerate all possible value ranges (double loop):

The outer loop i represents the minimum value of the current range.
The inner loop j represents the maximum value of the current range.
If <span>val[j] - val[i] ≤ k</span>, then use the prefix sum to calculate the total value within that range.
Since the array is sorted, once the condition is not met, we can directly break the inner loop.

Maintain and update the maximum total value.

Time Complexity:

Sorting requires
Calculating the prefix sum requires
Double loop enumeration of value ranges requires
The overall time complexity is

Space Complexity:

An additional prefix sum array is needed, with a space complexity of

Method 2: Sliding Window (Two Pointers) Method

Similarly, first sort the treasure box values.
Use two pointers to maintain a sliding window:

The right pointer continuously expands the window to include new treasure boxes in the total.
When the difference between the maximum and minimum values in the window exceeds k, move the left pointer to shrink the window.
Since the array is sorted, the value at the right pointer is the current maximum, and the value at the left pointer is the current minimum.

Maintain the maximum total value while sliding the window.

Time Complexity:

Sorting requires
The sliding window only needs to traverse the array once,
The overall time complexity is

Space Complexity:

Only the original array needs to be stored, with a space complexity of

For the data range of this problem (), both methods can pass, but the sliding window method has a clear advantage when handling larger datasets.

Example Code

Method 1: Prefix Sum

#include <algorithm>
#include <iostream>

// Array to store treasure box values
int val_arys[1005];
// Array to store prefix sums
int pre_sum[1005];
int main() {
    // Read in the number of treasure boxes n and the maximum value difference k
    int n, k;
    std::cin >> n >> k;
    // Read in the value of each treasure box
    for (int i = 0; i < n; i++) {
        std::cin >> val_arys[i];
    }
    // Sort the treasure box values for subsequent processing
    std::sort(val_arys, val_arys + n);
    // Calculate the first prefix sum
    pre_sum[0] = val_arys[0];
    // Calculate all prefix sums
    for (int i = 1; i < n; i++) {
        pre_sum[i] = pre_sum[i - 1] + val_arys[i];
    }
    // Record the maximum total value
    int max_sum = 0;
    // Enumerate all possible value ranges
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // If the current value range meets the condition (maximum minus minimum does not exceed k)
            if (val_arys[j] - val_arys[i] <= k) {
                // Use prefix sums to calculate the total value in the current range and update the maximum value
                max_sum = std::max(max_sum, pre_sum[j] - pre_sum[i] + val_arys[i]);
            } else {
                // Since the array is sorted, if the difference between the current j and i exceeds k
                // the subsequent differences will definitely be larger, so we can directly break the inner loop
                break;
            }
        }
    }
    // Output the result
    std::cout << max_sum;
    return 0;
}

Method 2: Sliding Window (Two Pointers)

#include <algorithm>
#include <iostream>

// Array to store treasure box values
int val_arys[1005];
int main() {
    // Read in the number of treasure boxes n and the maximum value difference k
    int n, k;
    std::cin >> n >> k;
    // Read in the value of each treasure box
    for (int i = 0; i < n; i++) {
        std::cin >> val_arys[i];
    }
    // Sort the treasure box values for sliding window use
    std::sort(val_arys, val_arys + n);
    // Record the maximum total value
    int max_sum = 0;
    // Left boundary of the sliding window
    int left = 0;
    // Current total value in the window
    int cur_sum = 0;
    // Move the right boundary of the sliding window to the right
    for (int right = 0; right < n; right++) {
        // Add the treasure box at the right boundary to the current total
        cur_sum += val_arys[right]; 
        // When the difference between the maximum and minimum values in the window exceeds k
        // continuously move the left boundary until the condition is met
        // Since the array is sorted, the value at the right position is definitely the current maximum
        // and the value at the left position is definitely the current minimum
        while(val_arys[right] - val_arys[left] > k) {
            // Remove the leftmost value from the window, need to subtract from the current sum
            cur_sum -= val_arys[left];
            // Move the left boundary to the right, shrinking the window range
            // Since the array is ordered, the new left position value must be greater than the previous value
            // This can gradually reduce the difference between the maximum and minimum values until the condition is met
            left++;
        }
        // Update the maximum total value
        max_sum = std::max(max_sum, cur_sum);
    }

    // Output the result
    std::cout << max_sum;
    return 0;
}

For detailed GESP syllabus, real question explanations, knowledge expansion, and practice lists, see:

[Pinned] [GESP] C++ Certification Learning Resource Summary

The “luogu-” series problems can be evaluated online in the Luogu Problem Bank.

The “bcqm-” series problems can be evaluated online in the Programming Enlightenment Problem Bank.