本文共 975 字,大约阅读时间需要 3 分钟。
你的初始能量为
P
,初始分数为0
,只有一包令牌。令牌的值为
token[i]
,每个令牌最多只能使用一次,可能的两种使用方法如下:
- 如果你至少有
token[i]
点能量,可以将令牌置为正面朝上,失去token[i]
点能量,并得到1
分。- 如果我们至少有
1
分,可以将令牌置为反面朝上,获得token[i]
点能量,并失去1
分。在使用任意数量的令牌后,返回我们可以得到的最大分数。
public int bagOfTokensScore(int[] tokens, int P) { if (tokens == null || tokens.length == 0) return 0; // 排序 Arrays.sort(tokens); int score = 0; // 分数 int MaxScore = 0; // 最大得分 int i = 0; for (i=0; i= tokens[i]) { P -= tokens[i]; // 能量点减少 score++; // 得分增加 } else break; } MaxScore = Math.max(MaxScore, score); // 能量点不足以翻开任何一张牌 if (score == 0) { return MaxScore; } int len = tokens.length; while (i != len) { score--; // 使用一分,翻开最后的令牌 P += tokens[len-1]; // 增加能量点 len--; // 表示最后一个令牌已经使用过 // 再次翻令牌 for (int j=i; j = tokens[j]) { P -= tokens[j]; score++; } else { i = j; // 记录下次要翻牌的位置 break; } } MaxScore = Math.max(MaxScore, score); // 再次比较 } return MaxScore; }
转载地址:http://icpoi.baihongyu.com/