{"id":7793,"date":"2020-12-12T23:35:13","date_gmt":"2020-12-13T07:35:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7793"},"modified":"2020-12-12T23:35:53","modified_gmt":"2020-12-13T07:35:53","slug":"leetcode-1686-stone-game-vi","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1686-stone-game-vi\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1686. Stone Game VI"},"content":{"rendered":"\n<p>Alice and Bob take turns playing a game, with Alice starting first.<\/p>\n\n\n\n<p>There are&nbsp;<code>n<\/code>&nbsp;stones in a pile. On each player&#8217;s turn, they can&nbsp;<strong>remove<\/strong>&nbsp;a stone from the pile and receive points based on the stone&#8217;s value. Alice and Bob may&nbsp;<strong>value the stones differently<\/strong>.<\/p>\n\n\n\n<p>You are given two integer arrays of length&nbsp;<code>n<\/code>,&nbsp;<code>aliceValues<\/code>&nbsp;and&nbsp;<code>bobValues<\/code>. Each&nbsp;<code>aliceValues[i]<\/code>&nbsp;and&nbsp;<code>bobValues[i]<\/code>&nbsp;represents how Alice and Bob, respectively, value the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;stone.<\/p>\n\n\n\n<p>The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play&nbsp;<strong>optimally<\/strong>.<\/p>\n\n\n\n<p>Determine the result of the game, and:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If Alice wins, return&nbsp;<code>1<\/code>.<\/li><li>If Bob wins, return&nbsp;<code>-1<\/code>.<\/li><li>If the game results in a draw, return&nbsp;<code>0<\/code>.<\/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> aliceValues = [1,3], bobValues = [2,1]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong>\nIf Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.\nBob can only choose stone 0, and will only receive 2 points.\nAlice wins.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> aliceValues = [1,2], bobValues = [3,1]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong>\nIf Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.\nDraw.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> aliceValues = [2,4,3], bobValues = [1,6,7]\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong>\nRegardless of how Alice plays, Bob will be able to have more points than Alice.\nFor example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.\nBob wins.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == aliceValues.length == bobValues.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= aliceValues[i], bobValues[i] &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Sort by the sum of stone values.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/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 Solution {\npublic:\n  int stoneGameVI(vector<int>& A, vector<int>& B) {\n    const int n = A.size();\n    vector<pair<int, int>> s(n);    \n    for (int i = 0; i < n; ++i)\n      s.emplace_back(A[i] + B[i], i);\n    sort(rbegin(s), rend(s));\n    int ans = 0;\n    for (int i = 0; i < n; ++i) {\n      int idx = s[i].second;\n      ans += (i &#038; 1 ? B[idx] : A[idx]) * (i &#038; 1 ? -1 : 1);\n    }\n    return ans < 0 ? -1 : (ans > 0);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Alice and Bob take turns playing a game, with Alice starting first. There are&nbsp;n&nbsp;stones in a pile. On each player&#8217;s turn, they can&nbsp;remove&nbsp;a stone from&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[27,88,177],"class_list":["post-7793","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-game","tag-greedy","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7793","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=7793"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7793\/revisions"}],"predecessor-version":[{"id":7795,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7793\/revisions\/7795"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}