三色球
普通解法
可以发现，如果可以兑换出张票，那么[1,x]张票都可以兑换出。
如果不可以兑换出x张票，那么[x,inf]张票都不可能兑换出。
所以这个答案是满足二分性质的。我们二分这个答案，考虑检查x张***是否可以兑换出来。
如果要换x张票，如果气球数量大于x，它就可以用于兑换其他气球。否则它需要被其他气球补全。所以按照这个逻辑去检查是否可行即可。
int solve(int a, int b, int c){
int l = min(min(a, b), c);
int r = max(max(a, b), c);
int ans = l;
while(l <= r){
int mid = (r+l)/2;
int ta = a-mid, tb = b-mid, tc = c-mid;
int ok = 0;
if(ta >= 0 && tb >= 0 && tc >= 0){
ok = 1;
}
if(ta < 0){
if(tb+2*ta >= 0 && tc+ta >= 0)ok = 1;
}
else if(tb < 0){
if(tc+2*tb >= 0 && ta+tb >= 0) ok = 1;
}else if(tc < 0){
if(ta+2*tc >= 0 && tb+tc >= 0) ok = 1;
}
if(ok) ans = mid, l = mid+1;
else r = mid-1;
}return ans;
}最优解法
贪心。设最少的气球是ret个，则一定可以兑换ret个彩票，然后用剩余的气球去填补用完的气球，可以填补出多少彩票可以直接算出来：比如现在0个红，b个黄，c个蓝，设兑换x个票，则 b-2x >= x, c-x >=x，得到x=min(b/3,c/2)。
int solve(int a, int b, int c) {
// write code here
int ret = min(min(a,b),c);
a-=ret;
b-=ret;
c-=ret;
if (a==0) {
ret += min(b/3, c/2);
}
else if (b==0) {
ret += min(c/3, a/2);
}
else {
ret += min(a/3, b/2);
}
return ret;
}
查看14道真题和解析