# Dongge ate grapes when he ate an algorithm problem!

2020-11-09 19:33:27

# Eating grapes

Learning algorithms depends on routines , Identify labuladong That's enough

If you're facing autumn moves , Dongge tells you something The routine in the written examination . Related to recommend ：

Eat grapes

-----------

Today, I did a piece called 「 Eat grapes 」 The subject of , Very interesting .

There are three kinds of grapes , Each one has `a, b, c` star , Now there are three people , The first man only ate the first and second grapes , The second man only ate the second and third grapes , The third man only ate the first and third grapes .

Now I'll give you the input `a, b, c` Three values , Please arrange it properly , Let three people eat all the grapes , The algorithm returns How many grapes should the most people eat .

The title form and force of Niu Ke net are different , I remove input and output processing , The core of the topic is to let you implement such a function ：

``````//  Input the number of grapes of three kinds , It could be very big , So use  long  type
//  Return to eat the most people to eat at least how many grapes
long solution(long a, long b, long c);
``````

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

### title

First of all, let's understand the topic , How do you make 「 The man who eats the most eats the least 」？

It can be understood in this way , We don't care about the restriction that everyone can only eat two specific grapes , How do you make 「 The man who eats the most eats the least 」？

obviously , Just average the score , Everyone eats `(a+b+c)/3` Grapes . Even if you can't divide , for instance `a+b+c=8`, That also needs to be as average as possible , It means eating alone 2 star , The other two eat 3 star .

Sum up ,「 The man who eats the most eats the least 」 Let's divide it as evenly as possible , And the number of grapes eaten by the person who eats the most is `(a+b+c)/3` The result of rounding up , That is to say `(a+b+c+2)/3`.

PS： Rounding up is a common algorithmic technique . In most programming languages , If you want to calculate `M` Divide `N`,`M / N` It's going to round down , If you want to round up , You can change to `(M+(N-1)) / N`.

Okay , I was just talking about a simple situation , Now consider if you add 「 Everyone can only eat two kinds of grapes 」 The limitation of , How do you do it? ？

in other words , Everyone can only eat two kinds of grapes , You have to As far as possible Divide equally among three people , So that the person who eats the most eats the least .

It's complicated , If you use `X, Y, Z` It means these three people , You'll find that they form a triangle ： You make someone eat a certain kind of grape more , There will be a cascade effect , Thinking about it is a headache , How about that ？

### Thought analysis

Anyway, everything depends on exhaustion , I started thinking about the possibility of brutality in backtracking algorithms ：

For every grape , Who might have eaten it ？ There are two possibilities , So I write a backtracking algorithm , List all the possibilities , And find the best value, OK ？

It's theoretically possible , But the complexity of brute force algorithms is usually exponential , If you take grapes as 「 Lead 」 To exhaust , Look at the variables `a, b, c` All are long Data of type , This complexity has made my spine furrow in cold sweat .

Well, this problem still has to be ingenious , The idea still has to go back to how 「 Distribute as evenly as possible 」 above , Then things get interesting .

If you count the grapes `a, b, c` As three lines , Their size is the length of the line , Think about what geometry they might form ？ Whether our purpose can be translated into 「 Divide the perimeter of the geometry as evenly as possible 」？

A graph of three lines , That's a triangle ？ Don't worry , We have learned , The triangle is to satisfy that the sum of the two sides is greater than the third side , hypothesis `a < b < c`, Well, there are two situations ：

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

If `a + b > c`, So you can make a triangle , Just take the midpoint of each side , We can divide the circumference of the triangle into three parts , And each copy contains two sides ： in other words , In this case , Three people are still able to divide all the grapes equally , The minimum number of grapes that people who eat the most can still eat is `(a+b+c+2)/3`.

If `a + b <= c`, These three edges can't form a closed figure , So we can put the longest side `c`「 break 」, That is to form a quadrilateral .

There are two situations ： For case one ,`a + b` and `c` When the gap is not big , You can see that it still allows three people to divide the quadrilateral equally , So the least grapes that people who eat the most can still eat `(a+b+c+2)/3`.

With `c` The increase of , There will be situation two , here `c > 2*(a+b)`, Because everyone's taste is limited , In order to share as much as possible ,`X` Eat at most `a` and `b`, and `c` The edge needs to be `Y` or `Z` divide equally , That is to say, at this time, the person who eats the most can eat at least the number of grapes `(c+1)/2`, That is to divide equally `c` Edge up round .

That's all , The code translates as follows ：

``````long solution(long a, long b, long c) {
long[] nums = new long[]{a, b, c};
Arrays.sort(nums);
long sum = a + b + c;

//  Can form a triangle , It can be divided equally
if (nums + nums > nums) {
return (sum + 2) / 3;
}
//  Can't make a triangle , In the case of bisecting the longest side
if (2 * (nums + nums) < nums) {
return (nums + 1) / 2;
}
//  Can't make a triangle , But it's still possible to divide it equally
return (sum + 2) / 3;
}
``````

thus , The problem was solved skillfully , The time complexity is just O(1), The key idea is how to divide as much as possible .

Who would have thought , Eating a grape depends on Geometry ？ Maybe that's the charm of algorithms ...

＿＿＿＿＿＿＿＿＿＿＿＿＿

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！