{"id":6357,"date":"2020-02-22T23:02:20","date_gmt":"2020-02-23T07:02:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6357"},"modified":"2020-02-22T23:02:48","modified_gmt":"2020-02-23T07:02:48","slug":"leetcode-1357-apply-discount-every-n-orders","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1357-apply-discount-every-n-orders\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1357. Apply Discount Every n Orders"},"content":{"rendered":"\n<p>There is&nbsp;a sale in a supermarket, there will be a&nbsp;<code>discount<\/code>&nbsp;every&nbsp;<code>n<\/code>&nbsp;customer.<br>There are some products in the supermarket where the id of the&nbsp;<code>i-th<\/code>&nbsp;product is&nbsp;<code>products[i]<\/code>&nbsp;and the price per unit of this product is&nbsp;<code>prices[i]<\/code>.<br>The system will count the number of customers and when the&nbsp;<code>n-th<\/code>&nbsp;customer arrive he\/she will have a&nbsp;<code>discount<\/code>&nbsp;on the bill. (i.e if the cost is&nbsp;<code>x<\/code>&nbsp;the new cost is&nbsp;<code>x - (discount * x) \/ 100<\/code>). Then the system will start counting customers again.<br>The customer orders a certain amount of each product where&nbsp;<code>product[i]<\/code>&nbsp;is the id of the&nbsp;<code>i-th<\/code>&nbsp;product the customer ordered and&nbsp;<code>amount[i]<\/code>&nbsp;is the number of units the customer ordered of that product.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>Cashier<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>Cashier(int n, int discount, int[] products, int[] prices)<\/code>&nbsp;Initializes the object with&nbsp;<code>n<\/code>, the&nbsp;<code>discount<\/code>, the&nbsp;<code>products<\/code>&nbsp;and their&nbsp;<code>prices<\/code>.<\/li><li><code>double&nbsp;getBill(int[] product, int[] amount)<\/code>&nbsp;returns the value of the bill and apply the discount if needed. Answers within&nbsp;<code>10^-5<\/code>&nbsp;of the actual value will be accepted as correct.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"Cashier\",\"getBill\",\"getBill\",\"getBill\",\"getBill\",\"getBill\",\"getBill\",\"getBill\"]\n[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]\n<strong>Output<\/strong>\n[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]\n<strong>Explanation<\/strong>\nCashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);\ncashier.getBill([1,2],[1,2]);                        \/\/ return 500.0, bill = 1 * 100 + 2 * 200 = 500.\ncashier.getBill([3,7],[10,10]);                      \/\/ return 4000.0\ncashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    \/\/ return 800.0, The bill was 1600.0 but as this is the third customer, he has a discount of 50% which means his bill is only 1600 - 1600 * (50 \/ 100) = 800.\ncashier.getBill([4],[10]);                           \/\/ return 4000.0\ncashier.getBill([7,3],[10,10]);                      \/\/ return 4000.0\ncashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); \/\/ return 7350.0, Bill was 14700.0 but as the system counted three more customers, he will have a 50% discount and the bill becomes 7350.0\ncashier.getBill([2,3,5],[5,3,2]);                    \/\/ return 2500.0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 10^4<\/code><\/li><li><code>0 &lt;= discount &lt;= 100<\/code><\/li><li><code>1 &lt;= products.length &lt;= 200<\/code><\/li><li><code>1 &lt;= products[i] &lt;= 200<\/code><\/li><li>There are&nbsp;<strong>not<\/strong>&nbsp;repeated elements in the array&nbsp;<code>products<\/code>.<\/li><li><code>prices.length == products.length<\/code><\/li><li><code>1 &lt;= prices[i] &lt;= 1000<\/code><\/li><li><code>1 &lt;= product.length &lt;= products.length<\/code><\/li><li><code>product[i]<\/code>&nbsp;exists in&nbsp;<code>products<\/code>.<\/li><li><code>amount.length == product.length<\/code><\/li><li><code>1 &lt;= amount[i] &lt;= 1000<\/code><\/li><li>At most&nbsp;<code>1000<\/code>&nbsp;calls will be made to&nbsp;<code>getBill<\/code>.<\/li><li>Answers within&nbsp;<code>10^-5<\/code>&nbsp;of the actual value will be accepted as correct.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(|Q|)<br>Space complexity: O(|P|)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Cashier {\npublic:\n  Cashier(int n, int discount, \n          vector<int>& products, \n          vector<int>& prices): n_(n), c_(0), discount_(discount) {\n    for (int i = 0; i < products.size(); ++i)\n      prices_[products[i]] = prices[i];\n  }\n\n  double getBill(vector<int> product, vector<int> amount) {\n    ++c_;\n    double bill = 0.0;\n    for (int i = 0; i < product.size(); ++i)\n      bill += prices_[product[i]] * amount[i];\n    if (c_ % n_ == 0)\n      bill *= 1.0 - discount_ \/ 100.0;\n    return bill;\n   }\nprivate:\n  int n_;\n  int c_;\n  int discount_;\n  array<int, 201> prices_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is&nbsp;a sale in a supermarket, there will be a&nbsp;discount&nbsp;every&nbsp;n&nbsp;customer.There are some products in the supermarket where the id of the&nbsp;i-th&nbsp;product is&nbsp;products[i]&nbsp;and the price per&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,179],"class_list":["post-6357","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6357"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6357\/revisions"}],"predecessor-version":[{"id":6359,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6357\/revisions\/6359"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}