思路讲解
题意概括——最少修改使任意3元组可以组成三角形
感觉这位的写的比较清楚，思路也比较易懂
排序什么的很好想，后面的有点难
总的来说就是不断选取（ai，ai+1）然后看以这个为母体，需要修改多少次，得到最少修改数，输出
这个具体的计算我们结合代码来讲
核心代码：
1
2
3
4
5
6
7
8
9
| 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代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #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;
}
|
心路历程（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为索引上界