题目描述
给定长度为 \(n\) 的序列 \(a\)，修改其中的一些数使得对于序列 \(a\) 中的任意三个数都能组成三角形，即两短边之和大于最长边。求出最少修改的数的个数。
解题思路
考虑到如果一个序列的最小的两个数之和大于第三个数，那么这个序列一定合法。那么进行修改的时候尽量修改最小连续的几个（或 \(0\) 个）数和最大连续的几个（或 \(0\) 个）数，使得中间没有被修改的序列为一个合法序列，被修改的数只需修改成中间这个合法序列中的数即可使整个序列合法。
那么这个问题就转化成了：找出 \(a\) 排序后的最长的连续合法子序列，若这个序列的长度为 \(k\)，则答案就是 \(n-k\)。
寻找这个连续序列的长度，考虑排序后双指针。令 \(l\) 和 \(r\) 分别为这个序列的首尾，若 \(a_l+a_{l+1}>a_r\) 则此序列合法，此时 r++，判断将 \(r\) 右移后是否还合法，合法继续右移，不合法就用合法序列的长度更新答案，然后右移 \(l\) 继续判断。特别地，当 \(r-l<3\) 时，此序列组不成三元组，无法判断合法，此时必须将 \(r\) 右移。
此外，如果整个序列都不存在合法的三元组，此时只需要选择两个数不变，剩下的数都修改为这两个数中较大的那个数即可满足合法，答案为 \(n-2\)。
排序时间复杂度 \(O(n\log n)\)，双指针时间复杂度 \(O(n)\)，总时间复杂度 \(O(n\log n)\)。
AC Code
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
int T,n;
int a[N];
int re()//防止作弊不放快读快写
void wr(int x)
signed main()
{T=re();while(T--){n=re();for(int i=1;i<=n;i++)a[i]=re();sort(a+1,a+n+1);int maxx=0;//答案 int l=1,r=3;//保证区间长度while(r<=n){while((a[l]+a[l+1]>a[r]||r-l<3)&&r<=n)//合法或者是长度小于 3 则 r 右移 r++;if(a[l]+a[l+1]>a[r-1])//合法序列：l~r-1，长度为 r-l maxx=max(maxx,r-l);l++;//不合法 l 右移}if(!maxx)wr(n-2),putchar('\n');elsewr(n-maxx),putchar('\n');}return 0;
}