枚举三个数

首先问题可以简化为，选择两个高度和，并且有，对于每个元素，如果那么该高度最终会被减去，如果该高度会被减去，同理如果该高度会被减去。

我们将数组从小到大排序，并画出删除区域，我们可以将消去的面积分为三部分计算，一部分是以为高，一部分是以为高，第三部分是以为高。并且我们可以推算得到，三个高度至少有两个高度出现在数组中。
证明：如果三个高度都不出现在数组内，我们可以提高或者到离其最近的高度。
如果有两个高度不出现在数组内。1.和没有出现，可以让和增加减小相同的大小，使得宽大的矩形的高增大到距离其最近的数组元素。2.和(或)没有出现，可以让二者同时增大直到一者的高度为数组出现元素。

有了以上证明，我们可以通过枚举出现在数组中的两个高度，用二分法搜索第三个高度的起点。

#include <bits/stdc++.h>
typedef long long ll;
class Solution {
public:
    /**
     * 返回两次操作后，数组元素之和的最小值
     * @param nums int整型vector 这你你需要操作的数组
     * @return long长整型
     */
    long long minimumValueAfterDispel(vector<int>& nums) {
        nums.push_back(0);
        sort(nums.begin(), nums.end()); // 从小到大
        ll ans = 0, sum = 0;
        for(auto i: nums)
            sum += i;
        // 假设h1 <= h2 <= h3
        for(ll i = 0; i < nums.size(); i++) { // 设第一个高度为nums[i]
            ll h1 = nums[i];
            for(ll j = i; j < nums.size(); j++){ // 第二个高度为nums[j]
                ll h2 = nums[j], h3 = nums[j] + nums[i];
                auto iter3 = lower_bound(nums.begin(), nums.end(), h3);
                ll idx3 = iter3 - nums.begin();
                ans = max(ans, (ll)(
                    (j - i) * h1 +
                    (idx3 - j) * h2 +
                    (nums.size() - idx3) * h3));
            }
            for(ll j = nums.size() - 1; j > i && nums[j] - nums[i] > nums[i]; j--){ // 第三个高度为nums[j]
                ll h3 = nums[j], h2 = nums[j] - nums[i];
                auto iter2 = lower_bound(nums.begin(), nums.end(), h2);
                ll idx2 = iter2 - nums.begin();
                ans = max(ans, (ll)(
                    (idx2 - i) * h1 +
                    (j - idx2) * h2 +
                    (nums.size() - j) * h3));
            }
        }
        for(ll i = 0; i < nums.size(); i++){ // 第二个高度为 nums[i]
            ll h2 = nums[i];
            for(ll j = i + 1; j < nums.size(); j++){ // 第三个高度为 nums[j]
                ll h3 = nums[j];
                if(h3 - h2 <= 0 || h3 - h2 >= h2)
                    continue;
                ll h1 = h3 - h2;
                auto iter1 = lower_bound(nums.begin(), nums.end(), h1);
                ll idx1 = iter1 - nums.begin();
                ans = max(ans, (ll)(
                    (i - idx1) * h1 +
                    (j - i) * h2 +
                    (nums.size() - j) * h3));
            }
        }
        return sum - ans;
    }
};