贪心、双指针

双指针注意边界问题。

大败而归，现在知道为啥错了。

将序列 $a$ 排序，不修改元素的情况下满足条件当且仅当 $a_1 + a_2 > a_n$。修改元素必定是修改一段前后缀，显然所有被修改的元素都修改成一个值时最优，由于最大值在式子中只有一个，最小值和次小值是两个，将前后缀中的数全部修改成最大值更优。

考虑以下数据。

4
1 1 2 2

如果把前后缀修改为 $1$，则得到的答案是 $2$；如果把前后缀修改为 $2$，则得到的答案是 $1$。最小值可能出现多次，让最小值尽量只出现一次的策略才是最优的贪心策略。故应该把被修改的数全部置为修改后数组的最大值。

双指针，注意边界，这里写个小模板。

    int l=1,r=1;//[l,r)
    while(l<=n){
        while(r<=n&&/*满足条件*/){
            /*更新答案*/
            /*扩展右边界 r 并维护信息*/
        }
        if(/*满足条件*/) /*更新答案*/
        /*扩展左边界 l 并维护信息*/
        /*注意扩展之后 l 可能不合法 不应在此更新答案*/
    }

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[200'005];
bool success(int l,int r){
    if(r-l<=2) return 1;
    return a[l]+a[l+1]>a[r-1];
}
void solution(){
    cin>>n,ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,r=1;
    while(l<=n){
        while(r<=n&&success(l,r)){
            ans=max(ans,r-l);
            ++r;
        }
        if(success(l,r)) ans=max(ans,r-l);
        ++l;
    }
    ans=n-ans;
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}