出题人题解 | T3

根据分析，最小值的最大值，可以联想到二分算法。需要考虑的有序性，在题目中寻找。

我们发现， $d_1+d_2+d_3$ 的结果是一定的，为 $n-3$ 。

考虑枚举三者之中最小的间隔，但是不确定元素不止有间隔本身大小，还有间隔之间的差值，这个思路舍弃。

现在考虑二分枚举三个间隔之间的最小的那个差值。

证明：

设 $d_1,d_2,d_3$ 三个间隔从小到大。

枚举三者之间最小差值为 $x$ ，那么第二个差值也是不小于 $x$ ，否则当前假设 $x$ 不成立。

设 $d_1 = l$ ,则如果要满足假设必须满足 $d_2$ 最小也是 $l+x$ ,同理 $d_3$ 最小也是 $l+2*x$ 。此外，对于 $d3$ 还可以通过 $n-3-l-(l+x)$ ，即为 $n-3-2*l-x$ 。

如果根据总长度算出来的理论高度，不小于满足最小间隔差值是 $x$ 要求的最小高度，即为 $n-3-2*l-x \ge l+2*x$ 化简得到 $n-3\ge 3*l+3*x$

看似存在两个不确定元素，间隔本身大小，还有间隔之间的差值，但是要求取最小值的最大值，也就是说 $x$ 要最大，满足题目的前提下是 $l = 0$ 。即 $n-3\ge 3*x$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,MOD = 1e9+7;
map<char,int>mp1,mp2;
int n,a[200];
string s,t;
bool check(int x){
    return 3*x <= n-3;
}
int main(){
    cin >>n;
    n -= 3;
    int l = 0,r = n / 3;
    while(l<r){
        int mid = (l+r+1) / 2;
        if(check(mid)) l = mid;//mid 满足要求，把l指向mid位置
        else r = mid-1;
    }
    cout << l;
    
    return 0;
}

当然这题你也可以用结论写，结论自己摸索哈。