贪心题目：令牌放置

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题令牌放置出处948. 令牌放置难度4 级题目描述要求初始能量为power \texttt{power}power初始分数为0 \texttt{0}0有一包令牌tokens \texttt{tokens}tokens其中tokens[i] \texttt{tokens[i]}tokens[i]是第i \texttt{i}i个令牌的值下标从0 \texttt{0}0开始。目标是得到最大分数。令牌可能的两种使用方法如下如果至少有token[i] \texttt{token[i]}token[i]点能量可以将令牌i \texttt{i}i正面朝上放置失去token[i] \texttt{token[i]}token[i]点能量并得到1 \texttt{1}1分。如果至少有1 \texttt{1}1分可以将令牌i \texttt{i}i反面朝上放置获得token[i] \texttt{token[i]}token[i]点能量并失去1 \texttt{1}1分。每个令牌最多只能使用一次可以按任意顺序使用。不需要使用所有令牌。返回在使用任意数量的令牌后可以得到的最大分数。示例示例 1输入tokens [100], power 50 \texttt{tokens [100], power 50}tokens [100], power 50输出0 \texttt{0}0解释无法使用唯一的令牌因为能量和分数都太低。示例 2输入tokens [100,200], power 150 \texttt{tokens [100,200], power 150}tokens [100,200], power 150输出1 \texttt{1}1解释令牌0 \texttt{0}0正面朝上能量变为50 \texttt{50}50分数变为1 \texttt{1}1。不必使用令牌1 \texttt{1}1因为无法使用它来提高分数。示例 3输入tokens [100,200,300,400], power 200 \texttt{tokens [100,200,300,400], power 200}tokens [100,200,300,400], power 200输出2 \texttt{2}2解释按下面顺序使用令牌可以得到2 \texttt{2}2分令牌0 \texttt{0}0正面朝上能量变为100 \texttt{100}100分数变为1 \texttt{1}1。令牌3 \texttt{3}3正面朝下能量变为500 \texttt{500}500分数变为0 \texttt{0}0。令牌1 \texttt{1}1正面朝上能量变为300 \texttt{300}300分数变为1 \texttt{1}1。令牌2 \texttt{2}2正面朝上能量变为0 \texttt{0}0分数变为2 \texttt{2}2。数据范围0 ≤ tokens.length ≤ 1000 \texttt{0} \le \texttt{tokens.length} \le \texttt{1000}0≤tokens.length≤10000 ≤ tokens[i], power 10 4 \texttt{0} \le \texttt{tokens[i], power} \texttt{10}^\texttt{4}0≤tokens[i], power104解法思路和算法为了得到最大分数应该优先考虑将令牌正面朝上放置失去能量并得到分数只有当剩余能量过低时才应该考虑将令牌反面朝上放置得到能量并失去分数。将令牌正面朝上放置时目标是将分数最大化。由于将任何一张令牌正面朝上放置都得到1 11分因此为了将分数最大化应该将正面朝上放置的令牌数量最大化。由于初始能量固定因此应该将失去的能量最小化优先将令牌值小的令牌正面朝上放置。将令牌反面朝上放置时目标是将能量最大化。由于将任何一张令牌反面朝上放置都失去1 11分因此为了将能量最大化应该将反面朝上放置的令牌能量之和最大化。由于初始分数固定因此应该优先将令牌值大的令牌正面朝上放置。优先将令牌正面朝上放置只有当无法继续将令牌正面朝上放置时才将令牌反面朝上放置。上述做法是贪心策略贪心策略的正确性说明如下。将令牌正面朝上放置时如果不优先使用令牌值小的令牌则可以正面朝上放置的令牌数量不变或减少不可能得到更多分数。将令牌反面朝上放置时如果不优先使用令牌值大的令牌则获得的能量不变或减少后续可以正面朝上放置的令牌数量不变或减少不可能得到更多分数。在可用能量固定的情况下优先将令牌正面朝上放置直到剩余的令牌都不能正面朝上放置因此对于固定的可用能量可以确保得到最大分数。由于每次放置令牌都取尚未使用的令牌中的值最小或值最大的令牌因此需要将数组tokens \textit{tokens}tokens按升序排序然后使用双指针分别从数组两端向中间遍历。用left \textit{left}left和right \textit{right}right分别表示两个指针初始时分别指向数组的左右两端。当left ≤ right \textit{left} \le \textit{right}left≤right时使用双指针遍历数组遍历过程中维护当前分数score \textit{score}score和最大分数maxScore \textit{maxScore}maxScore执行如下操作直到left right \textit{left} \textit{right}leftright或无法继续放置任何令牌时遍历结束。如果power ≥ tokens [ left ] \textit{power} \ge \textit{tokens}[\textit{left}]power≥tokens[left]则可以将tokens [ left ] \textit{tokens}[\textit{left}]tokens[left]正面朝上放置将power \textit{power}power减tokens [ left ] \textit{tokens}[\textit{left}]tokens[left]将left \textit{left}left向右移动一位将score \textit{score}score加1 11并用score \textit{score}score更新maxScore \textit{maxScore}maxScore。如果power tokens [ left ] \textit{power} \textit{tokens}[\textit{left}]powertokens[left]且score 0 \textit{score} 0score0则可以将tokens [ right ] \textit{tokens}[\textit{right}]tokens[right]反面朝上放置将power \textit{power}power加tokens [ right ] \textit{tokens}[\textit{right}]tokens[right]将right \textit{right}right向左移动一位将score \textit{score}score减1 11。如果power tokens [ left ] \textit{power} \textit{tokens}[\textit{left}]powertokens[left]且score 0 \textit{score} 0score0则不能继续放置任何令牌遍历结束。遍历结束时maxScore \textit{maxScore}maxScore即为最大分数。代码classSolution{publicintbagOfTokensScore(int[]tokens,intpower){intmaxScore0;intscore0;Arrays.sort(tokens);intleft0,righttokens.length-1;while(leftright(powertokens[left]||score0)){if(powertokens[left]){power-tokens[left];left;score;maxScoreMath.max(maxScore,score);}else{powertokens[right];right--;score--;}}returnmaxScore;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组tokens \textit{tokens}tokens的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间排序之后使用双指针遍历数组需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度O ( log ⁡ n ) O(\log n)O(logn)其中n nn是数组tokens \textit{tokens}tokens的长度。排序需要O ( log ⁡ n ) O(\log n)O(logn)的递归调用栈空间。