题解|牛牛的三角形

由于题目链接无法解析，我直接截图上来

这个题目要求找到序列中可以构成三角形的数

根据常识，三角形的组成条件是任意两边之差 a-b小于第三边 c

那么我们怎么去选边才能更高效呢？

很明显我们要两边之差 a-b尽可能的小是吧？这样 c才能匹配更大范围的数字。

那我们就要对给定数字进行排序，对排序后相邻的数字计算差值，进行比较和查找。

整体代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
using namespace std;
bool cmp(int *three);
int main(){
    
    int n=0;
    cin>>n;
    if(n<3) cout<<"No solution";
    vector<int> nums;
    int temp=0;
    for(int i=0;i<n;i++){
        cin>>temp;
        nums.push_back(temp);
    }
    sort(nums.begin(),nums.end(),greater<int>());	//对给定数字序列进行降序排序
    
    int three[3]={},i=0;
    for(;i<n-2;i++){
        for(int i=0;i<3;i++) three[i]=nums[i];	//每3个数字一组进行比较
        if(cmp(three)){
            for(int i=0;i<3;i++) cout<<three[i]<<' ';
            break;
        }
    }
    if(!cmp(three) && i==n-2) cout<<"No solution";
    
    return 0;
}
bool cmp(int *three){
    if(three[0]-three[1]<three[2]) return true;	//两边之差小于最小的第三边，则返回true
    else return false;
}