Codeforces Round 983 (Div. 2)—C. Trinity（最少修改使任意3元组可以组成三角形） · znzryb

## 思路讲解

[](https://www.luogu.com.cn/article/hax66nvh)

题意概括——**最少修改使任意3元组可以组成三角形**

感觉这位的写的比较清楚，思路也比较易懂

排序什么的很好想，后面的有点难

总的来说就是不断选取（ai，ai+1）然后看以这个为母体，需要修改多少次，得到最少修改数，输出

这个具体的计算我们结合代码来讲

核心代码：

```cpp
for(int i=0;i<n-2;++i) {
      ll l=lower_bound(A.begin(),A.end(),A[i+1])-A.begin();
      if(A[i]!=A[i+1])
          l-=1;
      if(l<0) l=0;
      ll r=lower_bound(A.begin(),A.end(),A[i]+A[i+1])-A.begin();
      ll lans=l+(n-r);
      ans=min(ans,lans);
}
```

l就是前面所有需要改成 $A[i+1]$ 的**数量**（忽略$A[i]$ ）

r就是后面所有需要改成 $A[i]+A[i+1]$ 的**起始索引**（哈哈，稍微有点混乱，不好意思）

## AC代码

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MAXN=static_cast<ll>(2e5+10);
ll T,n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vector<ll> A(n);
        for(int i=0;i<n;++i) {
            cin>>A[i];
        }
        sort(A.begin(),A.end());
        ll ans=MAXN;
        for(int i=0;i<n-2;++i) {
            ll l=lower_bound(A.begin(),A.end(),A[i+1])-A.begin();
            if(A[i]!=A[i+1])
                l-=1;
            if(l<0) l=0;
            ll r=lower_bound(A.begin(),A.end(),A[i]+A[i+1])-A.begin();
            ll lans=l+(n-r);
            ans=min(ans,lans);
        }
        cout<<ans<<"\n";
    }
    return 0;
}
// AC https://codeforces.com/contest/2032/submission/292856092
```

## 心路历程（WA，TLE，MLE……）

毕竟采用了我不太熟悉的0-based-index，还是稍微有点小翻车，

$lans=l+(n-r);$

我因为比较熟悉1-based，写成了 $n+1-r$ 但这在0-based里是不对的，n-r其实是$n-1-r+1$

$n-1$为索引上界