Hello! In this blog post, we will explore ways to contribute to society through the theme of helping the less fortunate by solving algorithm problems using C++. Algorithm problems play an important role in developing our problem-solving skills and are often a topic that comes up in actual job interviews.<\/p>\n
Every year, many people face social issues, and during Christmas, charity donations are made. Each donor can donate an amount of their choice, and through these donations, we aim to help a specific number of less fortunate individuals. However, each recipient has a maximum amount they can receive in donations.<\/p>\n
Given the array of donation amounts from the donors and the maximum amount that each recipient can receive, calculate the maximum total amount of donations all recipients can receive.<\/p>\n
N<\/code> (1 \u2264 N \u2264 1000)<\/li>\n- Second line:
N<\/code> integers representing the donation amounts from each donor A1<\/sub>, A2<\/sub>, ..., AN<\/sub><\/code> (1 \u2264 Ai<\/sub><\/code> \u2264 10000)<\/li>\n- Third line: the number of recipients
M<\/code> (1 \u2264 M \u2264 1000)<\/li>\n- Fourth line:
M<\/code> integers representing the maximum amount each recipient can receive B1<\/sub>, B2<\/sub>, ..., BM<\/sub><\/code> (1 \u2264 Bj<\/sub><\/code> \u2264 10000)<\/li>\n<\/ul>\nOutput Format<\/h3>\n
Output the maximum total amount of donations that all recipients can receive.<\/p>\n
Example Input<\/h2>\n\n5\n1500 2000 3000 4000 5000\n3\n2000 3000 10000\n<\/pre>\nExample Output<\/h2>\n\n10000\n<\/pre>\nProblem Solving Approach<\/h2>\n
The approach to solve this problem is as follows:<\/p>\n
\n- Sort the donation amounts from the donors and the maximum amounts each recipient can receive.<\/li>\n
- Check each donor’s maximum possible donation amount one by one and allocate it within the limits of each recipient’s maximum amount.<\/li>\n
- Accumulate the results of each donation to calculate the total amount donated.<\/li>\n<\/ol>\n
C++ Code Implementation<\/h2>\n
Below is the C++ code for the above approach:<\/p>\n
\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nint main() {\n int N;\n cout << \"Enter the number of donors: \";\n cin >> N;\n\n vector<int> donations(N);\n cout << \"Enter the donation amounts: \";\n for (int i = 0; i < N; i++) {\n cin >> donations[i];\n }\n\n int M;\n cout << \"Enter the number of recipients: \";\n cin >> M;\n\n vector<int> beneficiaries(M);\n cout << \"Enter the maximum amount each recipient can receive: \";\n for (int i = 0; i < M; i++) {\n cin >> beneficiaries[i];\n }\n\n \/\/ Sort the arrays of donors and recipients\n sort(donations.rbegin(), donations.rend());\n sort(beneficiaries.rbegin(), beneficiaries.rend());\n\n int totalDonated = 0;\n int donationIndex = 0;\n int beneficiaryIndex = 0;\n\n \/\/ Match donors with recipients\n while (donationIndex < N && beneficiaryIndex < M) {\n if (donations[donationIndex] <= beneficiaries[beneficiaryIndex]) {\n totalDonated += donations[donationIndex];\n donationIndex++;\n } else {\n totalDonated += beneficiaries[beneficiaryIndex];\n beneficiaryIndex++;\n }\n }\n\n cout << \"Maximum total amount donated: \" << totalDonated << endl;\n return 0;\n}\n<\/pre>\nCode Explanation<\/h2>\n
The above code works as follows:<\/p>\n
\n- Receive input for the number of donors and recipients, as well as their respective donation amounts and maximum amounts each recipient can receive.<\/li>\n
- Sort each array in descending order. This allows for comparison from the highest donations down to the lowest, enabling optimal allocation.<\/li>\n
- Operate such that each donor does not exceed the maximum amount or the highest donation for each recipient, allowing for as many donations as possible.<\/li>\n
- Calculate and output the total amount donated.<\/li>\n<\/ol>\n
Performance Validation and Testing<\/h2>\n
The code written should be validated against various input examples. Testing should also consider extreme cases (e.g., all donors donating the same amount) in addition to normal cases.<\/p>\n
Example Test Case<\/h3>\n\nInput:\n3\n3000 3000 3000\n4\n1500 3000 2000 1000\n\nOutput:\n9000\n<\/pre>\nIn the above code, the donors donate 3000, 3000, and 3000, while the recipients can receive 1500, 3000, 2000, and 1000 respectively. In this case, the maximum possible donation amount is 9000.<\/p>\n
In Conclusion<\/h2>\n
In this post, we explored how to develop logical thinking through an algorithm problem matching donors and recipients using C++. This is a commonly used problem-solving method in coding tests and I hope learning about issues that can contribute to society will enhance your programming skills. I wish you the best in your coding test preparations!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"