【codeforces】sweet Problem (规律，二分)_sweet problem 二分-CSDN博客

本文链接：https://blog.csdn.net/Skyed_blue/article/details/103348521

探讨了在有限数量的红、绿、蓝三色糖果中，如何通过最优分配策略使得每天消费两种不同颜色糖果的时间最大化。提出了两种解决方案，一种是基于规律的O(1)算法，另一种是基于二分枚举的O(lgn)算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

You have three piles of candies: red, green and blue candies:

the first pile contains only red candies and there are rr candies in it,
the second pile contains only green candies and there are gg candies in it,
the third pile contains only blue candies and there are bb candies in it.
Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can’t eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.

Input

The first line contains integer tt (1≤t≤10001≤t≤1000) — the number of test cases in the input. Then tt test cases follow.

Each test case is given as a separate line of the input. It contains three integers rr, gg and bb (1≤r,g,b≤1081≤r,g,b≤108) — the number of red, green and blue candies, respectively.

Output

Print tt integers: the ii-th printed integer is the answer on the ii-th test case in the input.

Example

input

Copy

6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8
output

Copy

1
2
2
10
5
9
Note

In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.

题意：

有 r 个红糖果，g 个绿糖果，b 个蓝糖果，1 <= r,g,b <= 10^8. 每天只能吃两个糖果，问最多可以吃多少天。

思路分析：

方法一：规律O(1)

先把r,g,b排序，从小到大为a,b,c如果a+b<=c,结果肯定输出a+b
否则输出(a+b+c)/2
原因：为了使天数最多，每次取最多和次多的两堆糖果，当次多的糖果吃到与最少的糖果相等时，把最多的糖果平分到最少和次多那一堆，（如果最多的为奇数，那么总共还剩一个，如果为偶数，所有糖果用完），所以说最优解剩下的糖果不超过两个(a+b>c时).

方法二：二分枚举 O(lgn)

为什么想到用二分呢？因为天数区间为[1, 1.5×10^8]. 一天吃两个糖果，最多可以有 3e8 个糖果. 因此最多可以吃 1.5e8 天。另外，我们假设糖果总数 n = 4. 如果是{4,0,0}，最多能吃0天；{3,1,0}，最多能吃1天；{2,1,1}，最多能吃2天。也就是说，n = 4 对应的天数区间为[0,2]. 我们需要求最多天数，即求该区间的有边界。
因此，我们可以二分枚举天数，利用天数计算出当前天r,g,b能组成的最大糖果总数(tot)，再与该天吃的糖果总数(mid×2)比较。

那么tot = min(mid,r) + min(mid,g) + min(mid,b). 因为在mid天每种糖果最多只能吃不超过mid个，并且糖果吃完后不能再吃。因此是min(mid,*).

如果 tot < mid*2 意味着当前吃了mid天后糖果数不够，天数可能取多了，缩小右边界；
如果 tot >= mid*2 意味着mid天数合法，即可以吃到mid天，于是向右逼近，取最大的mid.

直接看代码吧。

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int r, g, b;
		scanf("%d%d%d",&r, &g, &b);
		int L = 0, R = 3e8+5;
		int ans = 0;
		while(L < R)
		{
			int mid = L+R>>1;
			int tot = min(mid,r) + min(mid,g) + min(mid,b);	
			if(mid*2 > tot)	
			{
				R = mid;
			}
			else if(mid*2 <= tot)
			{
				L = mid+1;
				ans = max(ans,mid);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}