{"id":34304,"date":"2024-11-01T09:26:37","date_gmt":"2024-11-01T09:26:37","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34304"},"modified":"2024-11-01T10:57:47","modified_gmt":"2024-11-01T10:57:47","slug":"c-coding-test-course-line-up","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34304\/","title":{"rendered":"C++ Coding Test Course, Line Up"},"content":{"rendered":"<\/p>\n
Problem Description<\/h2>\n
\n 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. \n The problem is to find the minimum number of swaps required to sort the students in ascending order of height.\n <\/p>\n
Input Format<\/h2>\n
\n The first line contains the number of students N. (1 \u2264 N \u2264 1000) \n The second line contains the heights of N students separated by spaces. Each height is an integer between 1 and 1000 inclusive.\n <\/p>\n
\n To solve this problem, we will follow these steps:\n <\/p>\n
Step 1: Understand the Problem<\/h3>\n
\n The goal is to find the minimum number of swaps needed to sort the given students’ heights in ascending order. \n 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}. \n The objective is to count how many exchanges are needed in this process.\n <\/p>\n
Step 2: Approach<\/h3>\n
\n To find the optimal number of swaps, it is effective to sort the array step by step with each swap. \n We can solve this problem using the following method:\n <\/p>\n
\n
Pair the students’ heights with their indices and sort the given list.<\/li>\n
Compare each student’s current position with its sorted position.<\/li>\n
Students must be moved to their sorted positions through swaps, and already visited students will not be reconsidered.<\/li>\n<\/ol>\n
Step 3: Algorithm Implementation<\/h3>\n
\n #include \n #include \n #include \n \n using namespace std;\n\n \/\/ Define a structure: manage index and height as a pair\n struct Student {\n int index;\n int height;\n };\n\n \/\/ Define the swap function\n void swap(Student& a, Student& b) {\n Student temp = a;\n a = b;\n b = temp;\n }\n\n int minSwaps(vector& heights) {\n int n = heights.size();\n vector students(n);\n for (int i = 0; i < n; i++) {\n students[i] = {i, heights[i]};\n }\n \n \/\/ Sort the students by height\n sort(students.begin(), students.end(), [](Student a, Student b) {\n return a.height < b.height;\n });\n \n vector visited(n, false);\n int swapCount = 0;\n \n for (int i = 0; i < n; i++) {\n if (visited[i] || students[i].index == i) {\n continue;\n }\n \n \/\/ Calculate the size of the cycle\n int cycle_size = 0;\n int j = i;\n while (!visited[j]) {\n visited[j] = true;\n j = students[j].index;\n cycle_size++;\n }\n \n if (cycle_size > 0) {\n swapCount += (cycle_size - 1);\n }\n }\n return swapCount;\n }\n\n int main() {\n int n;\n cout << \"Enter the number of students: \";\n cin >> n;\n vector heights(n);\n\n cout << \"Enter the heights of the students: \";\n for (int i = 0; i < n; i++) {\n cin >> heights[i];\n }\n\n int result = minSwaps(heights);\n cout << \"Minimum number of swaps: \" << result << endl;\n return 0;\n }\n <\/int><\/bool><\/student><\/int><\/algorithm><\/vector><\/iostream><\/pre>\n
Step 4: Code Explanation<\/h3>\n
\n The above code shows a solution to the lineup problem written in C++. <\/p>\n
\n
Structure Student:<\/strong> Manages the index and height of students as a pair.<\/li>\n
swap Function:<\/strong> Swaps the information of two students.<\/li>\n
minSwaps Function:<\/strong> The main function that calculates the minimum number of swaps. It sorts the list of students and checks each visit to calculate cycles.<\/li>\n
Main Function:<\/strong> Accepts input from the user and outputs the results.<\/li>\n<\/ul>\n
Step 5: Testing and Validation<\/h3>\n
\n After writing the code, we perform tests with various cases. \n We must verify that the output matches the expected results for different inputs. \n For example, we can add the simplest test case to check for accuracy:\n <\/p>\n
\n Additionally, it is also important to check performance with larger inputs.\n <\/p>\n
Conclusion<\/h2>\n
\n Through this problem, we have improved our understanding of the concepts of swaps and sorting, the use of structures, and algorithm complexity. \n Since this type of problem frequently appears in C++ coding tests, we need to develop algorithmic thinking through sufficient practice.\n <\/p>\n