\n This is a problem to find out which pebbles would be the best choice when trying to take out m pebbles from a given n pebbles.
\n This problem can be solved using a Greedy Algorithm. The input consists of the weight of each pebble,
\n and the total weight of the pebbles taken out must not exceed K.\n<\/p>\n
\nInput:<\/strong> \nExample Input:<\/strong> \n To solve this problem, first, the weights of the given pebbles need to be sorted, and then the process of selecting the m heaviest pebbles should be performed. \n Now, let’s implement the C++ code based on the above algorithm.\n<\/p>\n \n The above C++ code takes input for the number of pebbles and the number of pebbles to be selected, and stores the weights of each pebble in an array. \n The time complexity of this algorithm is O(n log n), where n is the number of pebbles. The sorting process takes the largest share of the computation time. \n This problem is a good practice problem for learning the basics of greedy algorithms. Through the pebble selection problem, <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n – First line: Number of pebbles n (1 \u2264 n \u2264 100)
\n – Second line: Number of pebbles to take out m (1 \u2264 m \u2264 n)
\n – Third line: Weights of n pebbles (1 \u2264 weight \u2264 1000)
\nOutput:<\/strong>
\n – Calculate the total weight of the taken pebbles such that it is maximized to K.\n<\/p>\n3. Example<\/h2>\n
\n 5
\n 3
\n 1 2 3 4 5
\nExample Output:<\/strong>
\n 12 (3 + 4 + 5)\n<\/p>\n4. Algorithm Design<\/h2>\n
\n At this point, the total weight of the selected pebbles should be calculated and displayed as the result. The steps of the algorithm are as follows.\n<\/p>\n\n
5. Code Implementation<\/h2>\n
\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nint main() {\n int n, m;\n std::cout << \"Please enter the number of pebbles: \";\n std::cin >> n;\n std::cout << \"Please enter the number of pebbles to take out: \";\n std::cin >> m;\n\n std::vector<int> weights(n);\n std::cout << \"Please enter the weights of the pebbles (separated by spaces): \";\n for (int i = 0; i < n; ++i) {\n std::cin >> weights[i];\n }\n\n \/\/ Sort the weights of the pebbles\n std::sort(weights.begin(), weights.end());\n\n \/\/ Select the heaviest m pebbles\n int total_weight = 0;\n for (int i = n - m; i < n; ++i) {\n total_weight += weights[i];\n }\n\n std::cout << \"Total weight of selected pebbles: \" << total_weight << std::endl;\n\n return 0;\n}\n<\/code><\/pre>\n6. Code Explanation<\/h2>\n
\n Then, it uses the STL sort<\/code> function to sort the weights. It selects the heaviest m pebbles from the sorted array to calculate and display the total weight.\n<\/p>\n7. Algorithm Complexity Analysis<\/h2>\n
\n The space complexity is O(n), which is the memory needed to store the weights of the input pebbles.\n<\/p>\n8. Problem Solving Reflection<\/h2>\n
\n one can learn methods for making optimized choices. Similar problems frequently appear in actual coding tests, so
\n repetitive practice is necessary. I hope you gain more experience by solving various problems in the future.\n<\/p>\n