/* Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the items, given her budget. Given the price lists for the store's keyboards and USB drives, and Monica's budget, find and print the amount of money Monica will spend. If she doesn't have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items. To sum up, given two arrays and a target, find the pair which sum is closest to the target among any other pair. */ #include #include #include using namespace std; int getMoneySpent(vector keyboards, vector drives, int b) { sort(keyboards.begin(), keyboards.end()); sort(drives.begin(), drives.end()); int r = 0, c = drives.size() - 1; int money = -1, this_pair; while (true) { this_pair = keyboards[r] + drives[c]; if (this_pair > money && this_pair <= b) { money = this_pair; } if (this_pair == b) { break; } else if (this_pair < b) { ++r; if (keyboards.size() == r) { break; } } else { --c; if (c == -1) { break; } } } return money; } int main() { vector keyboard_prices = {932777, 851144, 575795, 345937, 126144, 35224, 581853, 746348, 766520, 802219, 406509, 160630, 880036, 537462, 648830, 191999, 899452, 719397, 623646, 271612, 131318, 316287, 309762, 845162, 201841, 476430, 909032, 669906, 760572, 402464, 676551, 298074, 301035, 625619, 184087, 154893, 756622, 373084, 474265, 209085, 225841, 695952, 616761, 944422, 40343, 995736, 326244, 450379, 468663, 252588, 147992, 442930, 984877, 847461, 209145, 206053, 130383, 952311, 203581, 341943, 769235, 986026, 425602, 838798, 565544, 808753, 21014 }; vector drives_prices = { 293983, 816277, 446427, 984129, 727183, 909949, 693077, 851983, 987591, 52587, 225212, 104439, 662468, 569112, 609820, 531599, 915305, 458067, 156398, 396879, 751968, 431308, 568397, 569427, 274728, 2077, 474542, 260768, 333852, 518397, 579444, 722379, 889201, 174196, 569434, 547005, 631865, 714621, 518865, 444728, 51178 }; int budget = 100520; int cost = getMoneySpent(keyboard_prices, drives_prices,budget); cout << "The most expensive pair of items she can afford cost together: " << cost << endl; return 0; }

Find a target pair