求解组成最大最小周长三角形

题意

给n个数,取3个组成三角形,且要求三角形的周长是最大的和最小的。

思路

求周长最大三角形,只要将n个数从大到小排序,然后取满足构成三角形的连续三个数即可。

求周长最小三角形,将n个数从小到大排序后,取连续的两个值然后二分第三条边。

代码

  int solve(int n, vector<int>& a) {//n个数,存在数组a中
        sort(all(a));
        LL Mx = 0, Mn = 1e18;
        //求最大三角形
        for(int i = 2; i < n; ++i) {
            if(a[i - 1] + a[i - 2] > a[i]) {
                Mx = max(Mx, (LL)a[i] + a[i - 1] + a[i - 2]);
            }
        }
        //求最小三角形
        for(int i = 1; i + 1 < n; ++i) {
            int p = upper_bound(a.begin(), a.begin() + i, a[i + 1] - a[i]) - a.begin();
            if(p < i) {
                Mn = min(Mn, (LL)a[p] + a[i] + a[i + 1]);
            }
        }
    }
上一篇:ASK


下一篇:AtCoder Regular Contest 107