Problem Description
N students are standing in line in a classroom. The height of each student is given in an array, and if they are standing in a different order than the given height, the students can swap their positions.
The problem is to find the minimum number of swaps required to sort the students in ascending order of height.
Input Format
The first line contains the number of students N. (1 ≤ N ≤ 1000)
The second line contains the heights of N students separated by spaces. Each height is an integer between 1 and 1000 inclusive.
Output Format
Print the minimum number of swaps.
Example Input/Output
Input:
5
5 3 2 4 1
Output:
4
Problem Solving
To solve this problem, we will follow these steps:
Step 1: Understand the Problem
The goal is to find the minimum number of swaps needed to sort the given students’ heights in ascending order.
For example, in the input above, the students were standing in the order {5, 3, 2, 4, 1} and need to be rearranged to {1, 2, 3, 4, 5}.
The objective is to count how many exchanges are needed in this process.
Step 2: Approach
To find the optimal number of swaps, it is effective to sort the array step by step with each swap.
We can solve this problem using the following method:
- Pair the students’ heights with their indices and sort the given list.
- Compare each student’s current position with its sorted position.
- Students must be moved to their sorted positions through swaps, and already visited students will not be reconsidered.
Step 3: Algorithm Implementation
#include
#include
#include
using namespace std;
// Define a structure: manage index and height as a pair
struct Student {
int index;
int height;
};
// Define the swap function
void swap(Student& a, Student& b) {
Student temp = a;
a = b;
b = temp;
}
int minSwaps(vector& heights) {
int n = heights.size();
vector students(n);
for (int i = 0; i < n; i++) {
students[i] = {i, heights[i]};
}
// Sort the students by height
sort(students.begin(), students.end(), [](Student a, Student b) {
return a.height < b.height;
});
vector visited(n, false);
int swapCount = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || students[i].index == i) {
continue;
}
// Calculate the size of the cycle
int cycle_size = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = students[j].index;
cycle_size++;
}
if (cycle_size > 0) {
swapCount += (cycle_size - 1);
}
}
return swapCount;
}
int main() {
int n;
cout << "Enter the number of students: ";
cin >> n;
vector heights(n);
cout << "Enter the heights of the students: ";
for (int i = 0; i < n; i++) {
cin >> heights[i];
}
int result = minSwaps(heights);
cout << "Minimum number of swaps: " << result << endl;
return 0;
}
Step 4: Code Explanation
The above code shows a solution to the lineup problem written in C++.
- Structure Student: Manages the index and height of students as a pair.
- swap Function: Swaps the information of two students.
- minSwaps Function: The main function that calculates the minimum number of swaps. It sorts the list of students and checks each visit to calculate cycles.
- Main Function: Accepts input from the user and outputs the results.
Step 5: Testing and Validation
After writing the code, we perform tests with various cases.
We must verify that the output matches the expected results for different inputs.
For example, we can add the simplest test case to check for accuracy:
Input:
3
3 1 2
Output:
2
Additionally, it is also important to check performance with larger inputs.
Conclusion
Through this problem, we have improved our understanding of the concepts of swaps and sorting, the use of structures, and algorithm complexity.
Since this type of problem frequently appears in C++ coding tests, we need to develop algorithmic thinking through sufficient practice.