题目描述
你正在玩一个单人游戏,面前放置着大小分别为 a
、b
和 c
的 三堆 石子。
每回合你都要从两个 不同的非空堆 中取出一颗石子,并在得分上加 1
分。当存在 两个或更多 的空堆时,游戏停止。
给你三个整数 a
、b
和 c
,返回可以得到的 最大分数 。
样例
输入:a = 2, b = 4, c = 6
输出:6
解释:石子起始状态是 (2, 4, 6) ,最优的一组操作是:
- 从第一和第三堆取,石子状态现在是 (1, 4, 5)
- 从第一和第三堆取,石子状态现在是 (0, 4, 4)
- 从第二和第三堆取,石子状态现在是 (0, 3, 3)
- 从第二和第三堆取,石子状态现在是 (0, 2, 2)
- 从第二和第三堆取,石子状态现在是 (0, 1, 1)
- 从第二和第三堆取,石子状态现在是 (0, 0, 0)
总分:6 分 。
输入:a = 4, b = 4, c = 6
输出:7
解释:石子起始状态是 (4, 4, 6) ,最优的一组操作是:
- 从第一和第二堆取,石子状态现在是 (3, 3, 6)
- 从第一和第三堆取,石子状态现在是 (2, 3, 5)
- 从第一和第三堆取,石子状态现在是 (1, 3, 4)
- 从第一和第三堆取,石子状态现在是 (0, 3, 3)
- 从第二和第三堆取,石子状态现在是 (0, 2, 2)
- 从第二和第三堆取,石子状态现在是 (0, 1, 1)
- 从第二和第三堆取,石子状态现在是 (0, 0, 0)
总分:7 分 。
输入:a = 1, b = 8, c = 8
输出:8
解释:最优的一组操作是连续从第二和第三堆取 8 回合,直到将它们取空。
注意,由于第二和第三堆已经空了,游戏结束,不能继续从第一堆中取石子。
提示:
1 <= a, b, c <= 10^5
算法1
模拟
- 当
a
,b
,c
三个数中存在2
个0
以上,直接返回ans
- 当
a
,b
,c
三个数中不存在2
个0
以上,则选出最大的两个数,两个数分别去掉1
,并且得分ans
加1
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int maximumScore(int a, int b, int c) {
int ans = 0;
while(true)
{
int cnt = 0;
if(a == 0) cnt ++;
if(b == 0) cnt ++;
if(c == 0) cnt ++;
if(cnt >= 2) break;
//选出最大的两个
if(a >= c && b >= c)
{
a --;
b --;
ans += 1;
} else if(a >= b && c >= b) {
a --;
c --;
ans += 1;
} else if(b >= a && c >= a) {
b --;
c --;
ans += 1;
}
}
return ans;
}
};
算法2
数学
假设a <= b <= c
,其中x
表示移除石子后剩下的总石子数量(最终会剩下一堆),那么总消耗的石子数量是(a + b + c- x)
,同时总消耗的石子数量一定是偶数个,因此移除石子的最大得分是(a + b + c - x) / 2
。
分两种情况讨论:
- 1、
a + b < c
我们可以让c
和a
配对,直到a
用完后,再让c
和b
配对,直到b
用完,最终c
一定满足c > 0
,因此最终剩下的总石子数量是x = (c - a - b)
- 2、
a + b >= c
我们可以让a
和b
中较大的一个和c
配对,直到c
用完,再让剩下的a’
和b’
中继续两两配对,这里也只有两个情况- (1)
a’
和b’
只相差一个,即a’
比b’
多一个 或者b’
比a’
多一个 - (2)
a’
和b’
相同
因此最终剩下的总石子数量是x = (c - a - b) % 2
(要么是1
,要么是0
)
- (1)
时间复杂度 $O(1)$
C++ 代码
class Solution {
public:
int maximumScore(int a, int b, int c) {
int d[] = {a, b, c};
sort(d, d + 3);
int x = 0;
if(d[0] + d[1] < d[2]) x = d[2] - d[0] - d[1];
else x = (a + b + c) % 2;
return (a + b + c - x) / 2;
}
};