Krammer's blog

https://leetcode.com/problems/maximum-score-from-removing-stones/ from Google

Thinking process:

There are other clever one line solutions, but we don’t need that after checking the constraints. All of the numbers are less than 10^5, so our solution can be O(NlogN) if it is just related to the number.

The solution can be greedy. We can always choose the min of the three numbers and the max of the three numbers. In this way, we’ll get most of the score. In C++, we can use multiset to achieve this.

Here is the code.

 1class Solution {
 2public:
 3    int maximumScore(int a, int b, int c) {
 4        multiset<int> ms;
 5        ms.insert(a);
 6        ms.insert(b);
 7        ms.insert(c);
 8        int ans = 0;
 9        while (ms.size() >= 2) {
10            ans++;
11            auto it = ms.begin();
12            int x = *it - 1;
13            auto it2 = ms.end();
14            it2--;
15            int y = *it2 - 1;
16            ms.erase(it);
17            ms.erase(it2);
18            if (x > 0) ms.insert(x);
19            if (y > 0) ms.insert(y);
20        }
21        return ans;
22        
23    }
24};

Editorial: LeetCode 1753 Maximum Score From Removing Stones