NC209583-牛牛与三角形

题目链接：https://ac.nowcoder.com/acm/problem/209583

题意：给定n个数，n个数中能构成的最大三角形周长值减去最小三角形周长值

思路：排序后，最小三角形的两个大边相邻，则二分第三个边，最大的三角形周长一定是相邻三个数，则逆序枚举找最大三角形周长。

构成三角形的条件：两个小边和大于最大边

反思:
lower_bound（a.begin(),a.end(),num）；二分查找递增数组，返回大于num的数的下标地址，否则返回a.end()；
upper_bound(a.begin(),a.end(),num);区别是 返回大于等于num的数组下标地址。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int formTriangle(int n, vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        int maxans=0,minans=0;
        for(int i=n-3;i>=0;i--){
            if(a[i]+a[i+1]>a[i+2]&&a[i+2]-a[i+1]<a[i]){
               maxans=a[i]+a[i+1]+a[i+2];
                break;
        }
    }
        for(int i=1;i+1<n;i++){
            int t=upper_bound(a.begin(),a.begin()+i,a[i+1]-a[i])-a.begin();
            if(a[t]+a[i]>a[i+1]&&t<i){
                minans=a[t]+a[i]+a[i+1];
                break;
        }
        }
            return maxans-minans;
    }
};
/*
5,[3,2,6,3,7]
8
1,[1,2,4,4]
1
*/

NC209583-牛牛与三角形

原文：https://www.cnblogs.com/abestxun/p/14366396.html