Learning C++ Programming from Scratch, Day 385: Solving the Number of Interception Systems for Missiles; Question Bank Answers; Third Method

1229 – Solving the Number of Interception Systems for Missiles

Analysis of the Missile Interception System Problem

This program addresses a classic missile interception problem, calculating the minimum number of systems required to intercept a given sequence of missiles. The program achieves this goal through a greedy algorithm and array processing.

Detailed Design Approach:

Data Structure Design:

Use an arraya to store the current interception height of each interception system
Variablek records the current number of systems
Variablep records the index of the found interceptable system

Input Processing:

Read the number of missilesn
Loop to read the height of each missilex

Interception Strategy:

For each missile, find the first system in the existing systems that can intercept it
If found, update the interception height of that system
If not found, add a new system
Use variablep as a search marker

Reference Code

#include <bits/stdc++.h>  // Include all standard library headers
using namespace std;     // Use standard namespace
/*Missile interception system problem: Calculate the minimum number of systems required to intercept a given sequence of missiles. Each system can only intercept missiles with heights not exceeding its current interception height.*/
// Define global variables
int a[1100];  // Array a stores the current interception height of each system
int n;        // Number of missiles
int i, j;     // Loop variables
int x;        // Current missile height
int p;        // Index of the found interceptable system
int k = 0;    // Current number of systems, initialized to 0
int main() {    // Read the number of missiles    cin >> n;
    // Loop to process each missile    for (i = 1; i <= n; i++) {        cin >> x;  // Read the current missile height        p = -1;    // Initialize p to -1, indicating no interceptable system found
        // Search for a system that can intercept the current missile in the existing systems        for (j = 1; j <= k; j++) {            // If the system can intercept the current missile            if (a[j] >= x) {                p = j;  // Record the system index                break;  // Exit the loop after finding the first interceptable system            }        }
        // Process based on the search result        if (p != -1) {  // If an interceptable system is found            a[p] = x;    // Update the interception height of that system        } else {         // If no interceptable system is found            k++;         // Increase the number of systems by 1            a[k] = x;    // Set the interception height of the new system to the current missile height        }    }
    // Output the minimum number of systems required    cout << k;
    return 0;  // Program ends normally

1. Program Overview

This program is used to solve the missile interception problem, calculating the minimum number of systems required to intercept a given sequence of missiles. Each interception system can only intercept missiles with heights not exceeding its current interception height, and the program efficiently solves for the minimum number of systems using a greedy algorithm.

2. Problem Description

Input:

First line: Number of missiles n
Second line: n integers representing the sequence of missile flight heights

Output: An integer representing the minimum number of interception systems required
Example:

Input:
```
5
50 40 60 30 10
```
Output: 2

3. Algorithm Principles

3.1 Data Structure

Use an arraya to store the current interception height of each system
Variablek records the current number of systems
Variablep as a search marker, records the index of the interceptable system

3.2 Greedy Strategy

For each missile:

Search for the first system in the existing systems that can intercept it
If found, update the interception height of that system
If not found, add a new system

The final value ofk is the minimum number of systems required

4. Code Analysis

4.1 Variable Description

Variable Name	Data Type	Description
a	int[1100]	Stores the interception height of the systems
n	int	Number of missiles
i,j	int	Loop counters
x	int	Current missile height
p	int	Index of the interceptable system
k	int	Number of systems

4.2 Key Code

Input Processing:

cin >> n;
for (i = 1; i <= n; i++) {
    cin >> x;
}

System Search:

if (a[j] >= x) {
    p = j;
break;
}

System Update:

if (p != -1) {
    a[p] = x;
} else {
    k++;
    a[k] = x;
}

5. Execution Flow

Read the number of missiles n
Initialize the number of systems k=0
For each missile:

Read height x
Search for interceptable systems in the existing systems
Update or add systems

Output the number of systems k

6. Learning Points

Greedy Algorithm: Understand the application of greedy strategies in resource allocation problems
Array Operations: Learn to traverse and update arrays
Loop Control: Master the use of nested loops
Marker Variables: Understand the usage scenarios of the variable p
Problem Modeling: Learn how to translate real-world problems into program logic

7. Frequently Asked Questions

Q: Why use a greedy algorithm?A: The greedy algorithm can efficiently find an approximate optimal solution, ensuring the minimum number of systems in this problem.

Q: Why is the array size set to 1100?A: To ensure it is large enough to handle larger input data.

Q: What is the time complexity of this algorithm?A: In the worst case, it is O(n²), as it may require traversing all systems for each missile.

Q: What happens if all missile heights are the same?A: Only one system is needed to intercept all missiles, and the program will output 1.