CF1734A Select Three Sticks 题解

· · 题解

首先我们要明白关于本题一个性质：

对于 3 根木棒，不妨设其长度为 a,b,c 且 a\le b\le c，想要用它们通过操作构成等边三角形（不妨设构成的等边三角形边长为 b），最小的操作次数如下：

t_{\min}=(b-a)+(c-b)=c-a

所以，我们只需将数列排序，并找到相邻的三个数使得第三个数减去第一个数的差最小即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,mn=INT_MAX; cin>>n;
    vector<int> a(n);
    for(auto &i:a)cin>>i;
    sort(a.begin(),a.end());
    for(int i=0;i<n-2;i++)
      mn=min(mn,a[i+2]-a[i]);
    cout<<mn<<endl;
  }
  return 0;
}