{"id":1754,"date":"2016-01-18T22:42:42","date_gmt":"2016-01-18T14:42:42","guid":{"rendered":"http:\/\/boweihe.me\/?p=1754"},"modified":"2016-01-18T22:42:42","modified_gmt":"2016-01-18T14:42:42","slug":"pat1037-magic-coupon-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1754","title":{"rendered":"PAT1037 Magic Coupon (25)"},"content":{"rendered":"

The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!
\nFor example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.
\nEach coupon and each product may be selected at most once. Your task is to get as much money back as possible.
\nInput Specification:<\/b>
\nEach input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105<\/sup>, and it is guaranteed that all the numbers will not exceed 230<\/sup>.
\nOutput Specification:<\/b>
\nFor each test case, simply print in a line the maximum amount of money you can get back.
\nSample Input:<\/b><\/p>\n

4\n1 2 4 -1\n4\n7 6 -2 -3\n<\/pre>\n
Sample Output:<\/b><\/p>\n
43<\/pre>\n
 
\n=====================================================
\n\u8fd9\u9053\u9898\u4e5f\u6ca1\u4ec0\u4e48\u6280\u672f\u542b\u91cf\uff0c\u5c31\u662f\u7ed9\u4f60\u4e00\u4e2aX\u5217\u4e00\u4e2aY\u5217\uff0c\u91cc\u9762\u8981\u51d1\u51fa\u6700\u5927\u7684\u79ef\u7684\u548c\u3002\u6709\u4e2a\u9650\u5236\u6761\u4ef6\uff0c\u5c31\u662f\u5546\u54c1\u6570\u91cf\u6709\u9650\uff0c\u6240\u4ee5\u53ef\u4ee5\u4ece\u5546\u54c1\u5165\u624b\u3002\u5c06\u5546\u54c1\u3001\u4f18\u60e0\u5238\u5168\u90e8\u6392\u5e8f\u540e\uff0c\u4ece\u5546\u54c1\u7684\u4e00\u6bb5\u5f00\u59cb\u5339\u914d\u80fd\u4ea7\u751f\u6700\u5927\u79ef\u7684\u4f18\u60e0\u5238\uff0c\u7d2f\u8ba1\u548c\uff0c\u5982\u679c\u78b0\u5230\u4e58\u51fa\u8d1f\u6570\u7684\u5c31\u6389\u4e2a\u5934\uff0c\u4ece\u672b\u7aef\u5f80\u56de\u627e\u3002\u56e0\u4e3a\u6c42\u5feb\uff0c\u6240\u4ee5\u4ee3\u7801\u5199\u7684\u591a\u4e86\u70b9\uff0c\u4f30\u8ba1\u8fd8\u80fd\u7cbe\u7b80…<\/p>\n
#include <iostream>\nusing namespace std;\nint compare(const void *a, const void *b)\n{\n\treturn (*(long*)a > *(long*)b) ? -1 : 1;\n}\nint main()\n{\n\tint NC, NP;\n\tcin >> NC;\n\tlong * coupons = new long[NC];\n\tfor (int i = 0; i < NC; i++)\n\t{\n\t\tcin >> coupons[i];\n\t}\n\tcin >> NP;\n\tlong * products = new long[NP];\n\tfor (int i = 0; i < NP; i++)\n\t{\n\t\tcin >> products[i];\n\t}\n\tqsort(coupons, NC, sizeof(long), compare);\n\tqsort(products, NP, sizeof(long), compare);\n\tint nc_index = 0;\n\tlong bonussum = 0;\n\tfor (int i = 0; i < NP; i++)\n\t{\n\t\tif (nc_index >= NC)\n\t\t\tbreak;\n\t\tif (products[i] < 0)\n\t\t\tbreak;\n\t\tlong bonus = coupons[nc_index] * products[i];\n\t\tif (bonus < 0)\n\t\t\tbreak;\n\t\tbonussum += bonus;\n\t\tnc_index++;\n\t}\n\tnc_index = NC - 1;\n\tfor (int i = NP - 1; i >= 0; i--)\n\t{\n\t\tif (nc_index < 0)\n\t\t\tbreak;\n\t\tif (products[i] > 0)\n\t\t\tbreak;\n\t\tlong bonus = coupons[nc_index] * products[i];\n\t\tif (bonus < 0)\n\t\t\tbreak;\n\t\tbonussum += bonus;\n\t\tnc_index--;\n\t}\n\tcout << bonussum;\n\treturn 0;\n}<\/pre>\n
\u91cc\u9762\u53ef\u4ee5\u770b\u5230\uff0c\u67d0\u4e2a\u76d1\u6d4b\u70b9\u8017\u65f6\u8fd8\u633a\u957f\u7684…\u4e0d\u8fc7\u6211\u7684\u539f\u5219\u662f\u591f\u7528\u5c31\u597d\u3002\u5982\u679c\u4f18\u60e0\u5238\u6570\u91cf\u8fdc\u591a\u4e8e\u5546\u54c1\u7684\u8bdd\uff0c\u8003\u8651\u53ea\u5bf9\u5546\u54c1\u6392\u5e8f\uff0c\u7136\u540e\u627e\u4f18\u60e0\u5238\u5c31\u884c\u4e86\uff1b\u53cd\u4e4b\u4ea6\u7136\u3002<\/p>\n
\u6d4b\u8bd5\u70b9<\/h2>\n\n\n\n\n\n\n\n\n\n\n
\u6d4b\u8bd5\u70b9<\/th>\n\u7ed3\u679c<\/th>\n\u7528\u65f6(ms)<\/th>\n\u5185\u5b58(kB)<\/th>\n\u5f97\u5206\/\u6ee1\u5206<\/th>\n<\/tr>\n<\/thead>\n
0<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n1<\/td>\n256<\/td>\n10\/10<\/td>\n<\/tr>\n
1<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n1<\/td>\n256<\/td>\n3\/3<\/td>\n<\/tr>\n
2<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n1<\/td>\n352<\/td>\n3\/3<\/td>\n<\/tr>\n
3<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n1<\/td>\n348<\/td>\n3\/3<\/td>\n<\/tr>\n
4<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n53<\/span><\/td>\n2560<\/span><\/td>\n3\/3<\/span><\/td>\n<\/tr>\n
5<\/td>\n\u7b54\u6848\u6b63\u786e<\/span><\/td>\n1<\/td>\n356<\/td>\n3\/3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-1754","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1754","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1754"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1754\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}